Sum of prefix scores of strings

Array String Trie Counting

60.8% acceptance

Feb 25, 2026

1193

111

You are given an array words of size n consisting of non-empty strings. We define the score of a string term as the number of strings words[i] such that term is a prefix of words[i]. Return an array answer of size n where answer[i] is the sum of scores of every non-empty prefix of words[i].

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn sum_prefix_scores(words: Vec<String>) -> Vec<i32> {
    let mut children: Vec<[i32; 26]> = vec![[-1i32; 26]];
    let mut count: Vec<i32> = vec![0];

    for word in &words {
      let mut node = 0usize;
      for c in word.bytes() {
        let idx = (c - b'a') as usize;
        if children[node][idx] == -1 {
          children[node][idx] = children.len() as i32;
          children.push([-1i32; 26]);
          count.push(0);
        }
        node = children[node][idx] as usize;
        count[node] += 1;
      }
    }

    let mut ans = Vec::with_capacity(words.len());
    for word in &words {
      let mut node = 0usize;
      let mut score = 0i32;
      for c in word.bytes() {
        let idx = (c - b'a') as usize;
        node = children[node][idx] as usize;
        score += count[node];
      }
      ans.push(score);
    }
    ans
  }
}