Welcome to Subscribe On Youtube

1065. Index Pairs of a String

Description

Given a string text and an array of strings words, return an array of all index pairs [i, j] so that the substring text[i...j] is in words.

Return the pairs [i, j] in sorted order (i.e., sort them by their first coordinate, and in case of ties sort them by their second coordinate).

 

Example 1:

Input: text = "thestoryofleetcodeandme", words = ["story","fleet","leetcode"]
Output: [[3,7],[9,13],[10,17]]

Example 2:

Input: text = "ababa", words = ["aba","ab"]
Output: [[0,1],[0,2],[2,3],[2,4]]
Explanation: Notice that matches can overlap, see "aba" is found in [0,2] and [2,4].

 

Constraints:

• 1 <= text.length <= 100
• 1 <= words.length <= 20
• 1 <= words[i].length <= 50
• text and words[i] consist of lowercase English letters.
• All the strings of words are unique.

Solutions

• Java
• C++
• Python
• Go

• class Trie {
      Trie[] children = new Trie[26];
      boolean isEnd = false;
  
      void insert(String word) {
          Trie node = this;
          for (char c : word.toCharArray()) {
              c -= 'a';
              if (node.children[c] == null) {
                  node.children[c] = new Trie();
              }
              node = node.children[c];
          }
          node.isEnd = true;
      }
  }
  
  class Solution {
      public int[][] indexPairs(String text, String[] words) {
          Trie trie = new Trie();
          for (String w : words) {
              trie.insert(w);
          }
          int n = text.length();
          List<int[]> ans = new ArrayList<>();
          for (int i = 0; i < n; ++i) {
              Trie node = trie;
              for (int j = i; j < n; ++j) {
                  int idx = text.charAt(j) - 'a';
                  if (node.children[idx] == null) {
                      break;
                  }
                  node = node.children[idx];
                  if (node.isEnd) {
                      ans.add(new int[] {i, j});
                  }
              }
          }
          return ans.toArray(new int[ans.size()][2]);
      }
  }
  

• class Trie {
  public:
      vector<Trie*> children;
      bool isEnd = false;
  
      Trie() {
          children.resize(26);
      }
  
      void insert(string word) {
          Trie* node = this;
          for (char c : word) {
              c -= 'a';
              if (!node->children[c]) node->children[c] = new Trie();
              node = node->children[c];
          }
          node->isEnd = true;
      }
  };
  
  class Solution {
  public:
      vector<vector<int>> indexPairs(string text, vector<string>& words) {
          Trie* trie = new Trie();
          for (auto w : words) trie->insert(w);
          int n = text.size();
          vector<vector<int>> ans;
          for (int i = 0; i < n; ++i) {
              Trie* node = trie;
              for (int j = i; j < n; ++j) {
                  int idx = text[j] - 'a';
                  if (!node->children[idx]) break;
                  node = node->children[idx];
                  if (node->isEnd) ans.push_back({i, j});
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def indexPairs(self, text: str, words: List[str]) -> List[List[int]]:
          words = set(words)
          n = len(text)
          return [
              [i, j] for i in range(n) for j in range(i, n) if text[i : j + 1] in words
          ]
  
  

• type Trie struct {
  	children [26]*Trie
  	isEnd    bool
  }
  
  func newTrie() *Trie {
  	return &Trie{}
  }
  
  func (this *Trie) insert(word string) {
  	node := this
  	for _, c := range word {
  		idx := int(c - 'a')
  		if node.children[idx] == nil {
  			node.children[idx] = newTrie()
  		}
  		node = node.children[idx]
  	}
  	node.isEnd = true
  }
  
  func indexPairs(text string, words []string) [][]int {
  	trie := newTrie()
  	for _, w := range words {
  		trie.insert(w)
  	}
  	n := len(text)
  	var ans [][]int
  	for i := range text {
  		node := trie
  		for j := i; j < n; j++ {
  			idx := int(text[j] - 'a')
  			if node.children[idx] == nil {
  				break
  			}
  			node = node.children[idx]
  			if node.isEnd {
  				ans = append(ans, []int{i, j})
  			}
  		}
  	}
  	return ans
  }
  

All Problems

All Solutions