Question

2416. Sum of Prefix Scores of Strings

中文文档

Description

You are given an array words of size n consisting of non-empty strings.

We define the score of a string word as the number of strings words[i] such that word is a prefix of words[i].

• For example, if words = ["a", "ab", "abc", "cab"], then the score of "ab" is 2, since "ab" is a prefix of both "ab" and "abc".

Return _an array _answer_ of size _n_ where _answer[i]_ is the sum of scores of every non-empty prefix of _words[i].

Note that a string is considered as a prefix of itself.

 

Example 1:

Input: words = ["abc","ab","bc","b"]
Output: [5,4,3,2]
Explanation: The answer for each string is the following:
- "abc" has 3 prefixes: "a", "ab", and "abc".
- There are 2 strings with the prefix "a", 2 strings with the prefix "ab", and 1 string with the prefix "abc".
The total is answer[0] = 2 + 2 + 1 = 5.
- "ab" has 2 prefixes: "a" and "ab".
- There are 2 strings with the prefix "a", and 2 strings with the prefix "ab".
The total is answer[1] = 2 + 2 = 4.
- "bc" has 2 prefixes: "b" and "bc".
- There are 2 strings with the prefix "b", and 1 string with the prefix "bc".
The total is answer[2] = 2 + 1 = 3.
- "b" has 1 prefix: "b".
- There are 2 strings with the prefix "b".
The total is answer[3] = 2.

Example 2:

Input: words = ["abcd"]
Output: [4]
Explanation:
"abcd" has 4 prefixes: "a", "ab", "abc", and "abcd".
Each prefix has a score of one, so the total is answer[0] = 1 + 1 + 1 + 1 = 4.

 

Constraints:

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] consists of lowercase English letters.

Solutions

Solution 1: Trie

Use a trie to maintain the prefixes of all strings and the occurrence count of each prefix.

Then, traverse each string, accumulating the occurrence count of each prefix.

The time complexity is $O(n \times m)$. Here, $n$ and $m$ are the length of the string array words and the maximum length of the strings in it, respectively.

class Trie:
  def __init__(self):
    self.children = [None] * 26
    self.cnt = 0

  def insert(self, w):
    node = self
    for c in w:
      idx = ord(c) - ord('a')
      if node.children[idx] is None:
        node.children[idx] = Trie()
      node = node.children[idx]
      node.cnt += 1

  def search(self, w):
    node = self
    ans = 0
    for c in w:
      idx = ord(c) - ord('a')
      if node.children[idx] is None:
        return ans
      node = node.children[idx]
      ans += node.cnt
    return ans


class Solution:
  def sumPrefixScores(self, words: List[str]) -> List[int]:
    trie = Trie()
    for w in words:
      trie.insert(w)
    return [trie.search(w) for w in words]

class Trie {
  private Trie[] children = new Trie[26];
  private int cnt;

  public void insert(String w) {
    Trie node = this;
    for (char c : w.toCharArray()) {
      c -= 'a';
      if (node.children[c] == null) {
        node.children[c] = new Trie();
      }
      node = node.children[c];
      ++node.cnt;
    }
  }

  public int search(String w) {
    Trie node = this;
    int ans = 0;
    for (char c : w.toCharArray()) {
      c -= 'a';
      if (node.children[c] == null) {
        return ans;
      }
      node = node.children[c];
      ans += node.cnt;
    }
    return ans;
  }
}

class Solution {
  public int[] sumPrefixScores(String[] words) {
    Trie trie = new Trie();
    for (String w : words) {
      trie.insert(w);
    }
    int[] ans = new int[words.length];
    for (int i = 0; i < words.length; ++i) {
      ans[i] = trie.search(words[i]);
    }
    return ans;
  }
}

class Trie {
private:
  vector<Trie*> children;
  int cnt;

public:
  Trie()
    : children(26)
    , cnt(0) {}

  void insert(string& w) {
    Trie* node = this;
    for (char c : w) {
      int idx = c - 'a';
      if (!node->children[idx]) node->children[idx] = new Trie();
      node = node->children[idx];
      ++node->cnt;
    }
  }

  int search(string& w) {
    Trie* node = this;
    int ans = 0;
    for (char c : w) {
      int idx = c - 'a';
      if (!node->children[idx]) return ans;
      node = node->children[idx];
      ans += node->cnt;
    }
    return ans;
  }
};

class Solution {
public:
  vector<int> sumPrefixScores(vector<string>& words) {
    Trie* trie = new Trie();
    for (auto& w : words) {
      trie->insert(w);
    }
    vector<int> ans;
    for (auto& w : words) {
      ans.push_back(trie->search(w));
    }
    return ans;
  }
};

type Trie struct {
  children [26]*Trie
  cnt    int
}

func newTrie() *Trie {
  return &Trie{}
}
func (this *Trie) insert(w string) {
  node := this
  for _, c := range w {
    c -= 'a'
    if node.children[c] == nil {
      node.children[c] = newTrie()
    }
    node = node.children[c]
    node.cnt++
  }
}

func (this *Trie) search(word string) int {
  node := this
  ans := 0
  for _, c := range word {
    c -= 'a'
    if node.children[c] == nil {
      return ans
    }
    node = node.children[c]
    ans += node.cnt
  }
  return ans
}

func sumPrefixScores(words []string) []int {
  trie := newTrie()
  for _, w := range words {
    trie.insert(w)
  }
  ans := make([]int, len(words))
  for i, w := range words {
    ans[i] = trie.search(w)
  }
  return ans
}

function sumPrefixScores(words: string[]): number[] {
  const map = new Map();

  for (const word of words) {
    const n = word.length;
    for (let i = 1; i <= n; i++) {
      const s = word.slice(0, i);
      map.set(s, (map.get(s) ?? 0) + 1);
    }
  }

  return words.map(word => {
    const n = word.length;
    let count = 0;
    for (let i = 1; i <= n; i++) {
      const s = word.slice(0, i);
      count += map.get(s);
    }
    return count;
  });
}

Solution 2

class Trie {
  children: Array<any>;
  cnt: number;

  constructor() {
    this.children = Array(26);
    this.cnt = 0;
  }

  insert(w: string): void {
    let node = this;
    for (const c of w) {
      const idx = c.charCodeAt(0) - 'a'.charCodeAt(0);
      if (!node.children[idx]) {
        node.children[idx] = new Trie();
      }
      node = node.children[idx];
      node.cnt++;
    }
  }

  search(w: string): number {
    let node = this;
    let ans = 0;
    for (const c of w) {
      const idx = c.charCodeAt(0) - 'a'.charCodeAt(0);
      if (!node.children[idx]) {
        return ans;
      }
      node = node.children[idx];
      ans += node.cnt;
    }
    return ans;
  }
}

function sumPrefixScores(words: string[]): number[] {
  const trie = new Trie();
  for (const w of words) {
    trie.insert(w);
  }
  let ans = [];
  for (const w of words) {
    ans.push(trie.search(w));
  }
  return ans;
}