Index pairs of a string

Array String Trie Sorting

68.6% acceptance

Mar 31, 2026

383

109

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

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn index_pairs(text: String, words: Vec<String>) -> Vec<Vec<i32>> {
    let text = text.as_bytes();
    let n = text.len();
    // Build a trie
    let mut trie: Vec<[i32; 26]> = vec![[-1i32; 26]];
    let mut is_end: Vec<bool> = vec![false];
    for word in &words {
      let mut node = 0usize;
      for &b in word.as_bytes() {
        let c = (b - b'a') as usize;
        if trie[node][c] == -1 {
          trie[node][c] = trie.len() as i32;
          trie.push([-1i32; 26]);
          is_end.push(false);
        }
        node = trie[node][c] as usize;
      }
      is_end[node] = true;
    }
    let mut result: Vec<Vec<i32>> = Vec::new();
    for i in 0..n {
      let mut node = 0usize;
      for j in i..n {
        let c = (text[j] - b'a') as usize;
        if trie[node][c] == -1 { break; }
        node = trie[node][c] as usize;
        if is_end[node] {
          result.push(vec![i as i32, j as i32]);
        }
      }
    }
    result
  }
}