Count prefix and suffix pairs ii

Array String Trie Rolling Hash String Matching Hash Function

28.1% acceptance

Feb 25, 2026

253

You are given a 0-indexed string array words. isPrefixAndSuffix(str1, str2) returns true if str1 is both a prefix and a suffix of str2, and false otherwise. Return an integer denoting the number of index pairs (i, j) such that i < j, and isPrefixAndSuffix(words[i], words[j]) is true.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_prefix_suffix_pairs(words: Vec<String>) -> i64 {
    // isPrefixAndSuffix(s, t) is true iff for every 0<=i<len(s):
    //   t[i] == s[i]  (prefix)  AND  t[len(t)-1-i-(len(s)-1-i)] == ... simplifies to:
    //   the pair-sequence of s, pairs[i]=(s[i], s[m-1-i]), is a prefix of t's pair-sequence.
    // So we maintain a trie keyed by character-pairs and count matching prior words.
    use std::collections::HashMap;
    struct TrieNode {
      children: HashMap<(u8, u8), usize>,
      count: i64,
    }
    let mut nodes: Vec<TrieNode> = vec![TrieNode { children: HashMap::new(), count: 0 }];
    let mut ans = 0i64;

    for word in &words {
      let w = word.as_bytes();
      let n = w.len();

      // Query: count prior words whose entire pair-sequence is a prefix of this word's
      let mut cur = 0usize;
      ans += nodes[cur].count; // length-0 words (none exist, always 0)
      for i in 0..n {
        let p = (w[i], w[n - 1 - i]);
        match nodes[cur].children.get(&p).copied() {
          Some(next) => { cur = next; ans += nodes[cur].count; }
          None => break,
        }
      }

      // Insert this word's pair-sequence into the trie
      cur = 0;
      for i in 0..n {
        let p = (w[i], w[n - 1 - i]);
        cur = if let Some(&c) = nodes[cur].children.get(&p) {
          c
        } else {
          let idx = nodes.len();
          nodes.push(TrieNode { children: HashMap::new(), count: 0 });
          nodes[cur].children.insert(p, idx);
          idx
        };
      }
      nodes[cur].count += 1;
    }
    ans
  }
}