Index Pairs of a String

1. Define the problem

Given a string text and a list of words , return every pair [i, j] such that the slice of text from position i through position j (both included) is exactly one of the words. Return the pairs sorted: smaller i first, and when i ties, smaller j first. Put all the words into a trie. Then start at each position of the text and walk forward through the trie. Every time you land on an end-of-word marker you have found a match, and the moment the next letter is missing from the trie you can stop early instead of checking the rest.

Constraints

1 ≤ text.length ≤ 100
1 ≤ words.length ≤ 20
1 ≤ words_i.length ≤ 50
text and words_i consist only of lowercase English letters

Example

Inputtext = "thestoryofleetcodeandme", words = ["story", "fleet", "leetcode"]

Output[[3, 7], [9, 13], [10, 17]]

Explanation "story" sits at positions 3 through 7, "fleet" at 9 through 13, and "leetcode" at 10 through 17. Note that the last two overlap, and both are reported.

2. Know the words first

In plain terms

Trie: A tree of letters where each stored word is a path from the top. Words sharing a start share a path.
Index pair: Two positions [i, j] marking a slice of the string, starting at position i and ending at position j, with both ends included.
Early exit: Stopping a loop as soon as it cannot possibly succeed. Here, if the trie has no link for the next letter, no longer word can match from this start.

3. Visualize the solution

Walking the text through the trie from each start position

0 a—

1 b—

2 a—

3 b—

4 a—

Statusinit

text = "ababa", words = ["ab", "aba"] are stored in a trie; start at i = 0.

What happens in this step

text = 'ababa'
words = ['ab', 'aba']
pairs = []
i = 0, node = root

The trie holds one path a-b-a, with an end marker after "ab" and after "aba".

Step 1 of 8

Steps to visualize

The row of cells is the text, one cell per character, with the position and letter as the label.
The value says what the trie said about that character: "node" means the path continues, "word" means a stored word ends there, "none" means the trie has no such link.
The frame marks the character currently being fed into the trie.
When a start position runs out of trie, the cells reset and the walk begins again from the next start.

4. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Walking the text through the trie from each start position

0 a—

1 b—

2 a—

3 b—

4 a—

Statusinit

text = "ababa", words = ["ab", "aba"] are stored in a trie; start at i = 0.

What happens in this step

text = 'ababa'
words = ['ab', 'aba']
pairs = []
i = 0, node = root

The trie holds one path a-b-a, with an end marker after "ab" and after "aba".

Step 1 of 8

5. Solution

Solution

solution.tsTypeScript

function indexPairs(text, words) {
  class TrieNode {
    constructor() {
      this.children = {};
      this.isEnd = false;
    }
  }

  const root = new TrieNode();

  for (const word of words) {
    let node = root;
    for (const ch of word) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
      }
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  const pairs = [];

  for (let i = 0; i < text.length; i++) {
    let node = root;
    for (let j = i; j < text.length; j++) {
      node = node.children[text[j]];
      if (!node) {
        break;
      }
      if (node.isEnd) {
        pairs.push([i, j]);
      }
    }
  }

  return pairs;
}

Time: O(n * m) where n is the length of text and m is the longest word
Space: O(total letters across all words)

6. Test cases

Test cases

Input	Expected	Covers
`text = "thestoryofleetcodeandme", words = ["story", "fleet", "leetcode"]`	`[[3, 7], [9, 13], [10, 17]]`	example from the docstring, including two overlapping matches
`text = "ababa", words = ["aba", "ab"]`	`[[0, 1], [0, 2], [2, 3], [2, 4]]`	one word inside another, matching several times
`text = "abcd", words = ["xyz"]`	`[]`	no word appears in the text at all
`text = "abcd", words = []`	`[]`	an empty word list, so the trie is empty
`text = "aaa", words = ["a"]`	`[[0, 0], [1, 1], [2, 2]]`	a one-letter word matching at every position
`text = "abc", words = ["abc", "abcd"]`	`[[0, 2]]`	a word longer than the text can never match

Index Pairs of a String