Longest common suffix queries

Array String Trie

35.9% acceptance

Feb 25, 2026

190

You are given two arrays of strings wordsContainer and wordsQuery. For each wordsQuery[i], you need to find a string from wordsContainer that has the longest common suffix with wordsQuery[i]. If there are two or more strings in wordsContainer that share the longest common suffix, find the string that is the smallest in length. If there are two or more such strings that have the same smallest length, find the one that occurred earlier in wordsContainer. Return an array of integers ans, where ans[i] is the index of the string in wordsContainer that has the longest common suffix with wordsQuery[i].

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn string_indices(words_container: Vec<String>, words_query: Vec<String>) -> Vec<i32> {
    // Build a trie of reversed strings from wordsContainer
    // Each node stores the best (shortest length, earliest index) container string
    let n = words_container.len();
    // Find shortest container string for "no match" case
    let default_idx = (0..n).min_by_key(|&i| (words_container[i].len(), i)).unwrap();
    
    // Trie with 26 children
    let mut trie: Vec<[i32; 26]> = vec![[-1i32; 26]];
    let mut best: Vec<(usize, usize)> = vec![(usize::MAX, usize::MAX)]; // (len, idx)
    
    for (i, w) in words_container.iter().enumerate() {
      let mut node = 0usize;
      let len = w.len();
      // Update best at each node with this container string
      if (len, i) < best[node] { best[node] = (len, i); }
      for &b in w.as_bytes().iter().rev() {
        let c = (b - b'a') as usize;
        if trie[node][c] == -1 {
          trie[node][c] = trie.len() as i32;
          trie.push([-1i32; 26]);
          best.push((usize::MAX, usize::MAX));
        }
        node = trie[node][c] as usize;
        if (len, i) < best[node] { best[node] = (len, i); }
      }
    }
    
    words_query.iter().map(|q| {
      let mut node = 0usize;
      let mut ans_idx = default_idx;
      // Find best at deepest reachable node
      if best[node].1 != usize::MAX { ans_idx = best[node].1; }
      for &b in q.as_bytes().iter().rev() {
        let c = (b - b'a') as usize;
        if trie[node][c] == -1 { break; }
        node = trie[node][c] as usize;
        if best[node].1 != usize::MAX { ans_idx = best[node].1; }
      }
      ans_idx as i32
    }).collect()
  }
}