Problem

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

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).

Examples

Example 1:

1
2

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

Example 2:

1
2
3

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.

Solution

Method 1 – Trie with Brute Force Search

Intuition

We want to efficiently find all substrings of text that match any word in words. A Trie allows us to quickly check for any word starting at each position in text.

Approach

  1. Build a Trie from all words in words.
  2. For each index i in text, start from i and traverse the Trie as long as characters match:
    • If a Trie node is marked as the end of a word, record the pair [i, j].
    • Continue until no further match is possible.
  3. Collect all pairs and sort them by the required order.

Code

 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

struct TrieNode {
    TrieNode* nxt[26] = {};
    bool end = false;
};
class Solution {
public:
    vector<vector<int>> indexPairs(string text, vector<string>& words) {
        TrieNode* root = new TrieNode();
        for (auto& w : words) {
            TrieNode* cur = root;
            for (char c : w) {
                int i = c - 'a';
                if (!cur->nxt[i]) cur->nxt[i] = new TrieNode();
                cur = cur->nxt[i];
            }
            cur->end = true;
        }
        vector<vector<int>> ans;
        int n = text.size();
        for (int i = 0; i < n; ++i) {
            TrieNode* cur = root;
            for (int j = i; j < n; ++j) {
                int idx = text[j] - 'a';
                if (!cur->nxt[idx]) break;
                cur = cur->nxt[idx];
                if (cur->end) 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

type TrieNode struct {
    nxt [26]*TrieNode
    end bool
}

func indexPairs(text string, words []string) [][]int {
    root := &TrieNode{}
    for _, w := range words {
        cur := root
        for _, c := range w {
            idx := c - 'a'
            if cur.nxt[idx] == nil {
                cur.nxt[idx] = &TrieNode{}
            }
            cur = cur.nxt[idx]
        }
        cur.end = true
    }
    var ans [][]int
    n := len(text)
    for i := 0; i < n; i++ {
        cur := root
        for j := i; j < n; j++ {
            idx := text[j] - 'a'
            if cur.nxt[idx] == nil {
                break
            }
            cur = cur.nxt[idx]
            if cur.end {
                ans = append(ans, []int{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

class TrieNode {
    TrieNode[] nxt = new TrieNode[26];
    boolean end = false;
}
class Solution {
    public int[][] indexPairs(String text, String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode cur = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (cur.nxt[i] == null) cur.nxt[i] = new TrieNode();
                cur = cur.nxt[i];
            }
            cur.end = true;
        }
        List<int[]> ans = new ArrayList<>();
        int n = text.length();
        for (int i = 0; i < n; ++i) {
            TrieNode cur = root;
            for (int j = i; j < n; ++j) {
                int idx = text.charAt(j) - 'a';
                if (cur.nxt[idx] == null) break;
                cur = cur.nxt[idx];
                if (cur.end) ans.add(new int[]{i, j});
            }
        }
        return ans.toArray(new int[0][]);
    }
}
 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

class TrieNode {
    val nxt = Array<TrieNode?>(26) { null }
    var end = false
}
class Solution {
    fun indexPairs(text: String, words: Array<String>): Array<IntArray> {
        val root = TrieNode()
        for (w in words) {
            var cur = root
            for (c in w) {
                val i = c - 'a'
                if (cur.nxt[i] == null) cur.nxt[i] = TrieNode()
                cur = cur.nxt[i]!!
            }
            cur.end = true
        }
        val ans = mutableListOf<IntArray>()
        val n = text.length
        for (i in 0 until n) {
            var cur = root
            for (j in i until n) {
                val idx = text[j] - 'a'
                if (cur.nxt[idx] == null) break
                cur = cur.nxt[idx]!!
                if (cur.end) ans.add(intArrayOf(i, j))
            }
        }
        return ans.toTypedArray()
    }
}
 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

class TrieNode:
    def __init__(self):
        self.nxt = [None] * 26
        self.end = False
class Solution:
    def indexPairs(self, text: str, words: list[str]) -> list[list[int]]:
        root = TrieNode()
        for w in words:
            cur = root
            for c in w:
                i = ord(c) - ord('a')
                if not cur.nxt[i]:
                    cur.nxt[i] = TrieNode()
                cur = cur.nxt[i]
            cur.end = True
        ans = []
        n = len(text)
        for i in range(n):
            cur = root
            for j in range(i, n):
                idx = ord(text[j]) - ord('a')
                if not cur.nxt[idx]:
                    break
                cur = cur.nxt[idx]
                if cur.end:
                    ans.append([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

struct TrieNode {
    nxt: [Option<Box<TrieNode>>; 26],
    end: bool,
}
impl TrieNode {
    fn new() -> Self {
        Self { nxt: Default::default(), end: false }
    }
}
fn index_pairs(text: &str, words: Vec<&str>) -> Vec<(usize, usize)> {
    let root = Box::new(TrieNode::new());
    for w in words {
        let mut cur = &root;
        for c in w.chars() {
            let i = (c as u8 - b'a') as usize;
            cur = cur.nxt[i].get_or_insert_with(|| Box::new(TrieNode::new()));
        }
        cur.end = true;
    }
    let n = text.len();
    let text = text.as_bytes();
    let mut ans = vec![];
    for i in 0..n {
        let mut cur = &root;
        for j in i..n {
            let idx = (text[j] - b'a') as usize;
            if cur.nxt[idx].is_none() { break; }
            cur = cur.nxt[idx].as_ref().unwrap();
            if cur.end { ans.push((i, j)); }
        }
    }
    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

class TrieNode {
  nxt: (TrieNode | null)[] = Array(26).fill(null);
  end = false;
}
class Solution {
  indexPairs(text: string, words: string[]): number[][] {
    const root = new TrieNode();
    for (const w of words) {
      let cur = root;
      for (const c of w) {
        const i = c.charCodeAt(0) - 97;
        if (!cur.nxt[i]) cur.nxt[i] = new TrieNode();
        cur = cur.nxt[i]!;
      }
      cur.end = true;
    }
    const ans: number[][] = [];
    const n = text.length;
    for (let i = 0; i < n; ++i) {
      let cur = root;
      for (let j = i; j < n; ++j) {
        const idx = text.charCodeAt(j) - 97;
        if (!cur.nxt[idx]) break;
        cur = cur.nxt[idx]!;
        if (cur.end) ans.push([i, j]);
      }
    }
    return ans;
  }
}

Complexity

  • ⏰ Time complexity: O(n * L) — n is the length of text, L is the sum of all word lengths (since we may traverse up to the length of the longest word for each position).
  • 🧺 Space complexity: O(L) — For the Trie, where L is the total length of all words.