Skip to content

1065. Index Pairs of a String

  • Time: $O(|\texttt{text}|^2 \cdot \max(|\texttt{words[i]}|))$
  • Space: $O(n\log(\Sigma |\texttt{sweetness[i]}|))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
struct TrieNode {
  vector<shared_ptr<TrieNode>> children;
  bool isWord = false;
  TrieNode() : children(26) {}
};

class Solution {
 public:
  vector<vector<int>> indexPairs(string text, vector<string>& words) {
    vector<vector<int>> ans;
    shared_ptr<TrieNode> root = make_shared<TrieNode>();

    for (const string& word : words) {
      shared_ptr<TrieNode> node = root;
      for (const char c : word) {
        const int i = c - 'a';
        if (node->children[i] == nullptr)
          node->children[i] = make_shared<TrieNode>();
        node = node->children[i];
      }
      node->isWord = true;
    }

    for (int i = 0; i < text.length(); ++i) {
      shared_ptr<TrieNode> node = root;
      for (int j = i; j < text.length(); j++) {
        const int index = text[j] - 'a';
        if (node->children[index] == nullptr)
          break;
        node = node->children[index];
        if (node->isWord)
          ans.push_back({i, j});
      }
    }

    return ans;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class TrieNode {
  public TrieNode[] children = new TrieNode[26];
  public boolean isWord = false;
}

class Solution {
  public int[][] indexPairs(String text, String[] words) {
    List<int[]> ans = new ArrayList<>();
    TrieNode root = new TrieNode();

    for (final String word : words) {
      TrieNode node = root;
      for (final char c : word.toCharArray()) {
        final int i = c - 'a';
        if (node.children[i] == null)
          node.children[i] = new TrieNode();
        node = node.children[i];
      }
      node.isWord = true;
    }

    for (int i = 0; i < text.length(); ++i) {
      TrieNode node = root;
      for (int j = i; j < text.length(); ++j) {
        final int index = text.charAt(j) - 'a';
        if (node.children[index] == null)
          break;
        node = node.children[index];
        if (node.isWord)
          ans.add(new int[] {i, j});
      }
    }

    return ans.toArray(int[][] ::new);
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class TrieNode:
  def __init__(self):
    self.children: dict[str, TrieNode] = collections.defaultdict(TrieNode)
    self.isWord = False


class Solution:
  def indexPairs(self, text: str, words: list[str]) -> list[list[int]]:
    ans = []
    root = TrieNode()

    for word in words:
      node: TrieNode = root
      for c in word:
        node = node.children.setdefault(c, TrieNode())
      node.isWord = True

    # Scan each text[i..j].
    for i in range(len(text)):
      node: TrieNode = root
      for j in range(i, len(text)):
        c = text[j]
        if c not in node.children:
          break
        node = node.children[c]
        if node.isWord:
          ans.append([i, j])

    return ans