字符串前缀分数之和

2416。字符串前缀分数之和

难度：难

主题：数组、字符串、Trie、计数

给你一个大小为 n 的单词数组，由 非空 字符串组成。

我们将字符串单词的分数定义为字符串单词[i]的数量，这样单词就是单词[i]的前缀。

• 例如，如果words = ["a", "ab", "abc", "cab"]，那么"ab"的分数是2，因为"ab"是"ab"和"ab"的前缀“abc”。

返回大小为n的数组答案，其中answer[i]是单词[i]的每个非空前缀分数的总和。

注意字符串被视为其自身的前缀。

示例1：

• 输入：words = ["abc","ab","bc","b"]
• 输出： [5,4,3,2]
• 解释： 每个字符串的答案如下：
  • “abc”有 3 个前缀：“a”、“ab”和“abc”。
  • 有 2 个带有前缀“a”的字符串，2 个带有前缀“ab”的字符串，1 个带有前缀“abc”的字符串。
  • 总数为答案[0] = 2 + 2 + 1 = 5。
  • “ab”有 2 个前缀：“a”和“ab”。
  • 有 2 个带有前缀“a”的字符串，以及 2 个带有前缀“ab”的字符串。
  • 总数为答案[1] = 2 + 2 = 4。
  • “bc”有 2 个前缀：“b”和“bc”。
  • 有 2 个带有前缀“b”的字符串，1 个带有前缀“bc”的字符串。
  • 总数为答案[2] = 2 + 1 = 3。
  • “b”有 1 个前缀：“b”。
  • 有 2 个字符串带有前缀“b”。
  • 总数为答案[3] = 2。

示例2：

• 输入：words = ["abcd"]
• 输出： [4]
• 说明：
  • “abcd”有 4 个前缀：“a”、“ab”、“abc”和“abcd”。
  • 每个前缀的得分为 1，因此总数为 answer[0] = 1 + 1 + 1 + 1 = 4。

约束：

• 1
• 1
• words[i] 由小写英文字母组成。

提示：

1. 什么样的数据结构可以让您有效地跟踪每个前缀的分数？
2. 使用特里树。将所有单词插入其中，并在每个节点处保留一个计数器，该计数器会告诉您我们访问每个前缀的次数。

解决方案：

我们可以使用 Trie 数据结构，它对于处理前缀特别有效。 Trie 中的每个节点都代表单词的一个字母，我们将在每个节点维护一个计数器来存储遇到该前缀的次数。这使我们能够通过计算有多少个单词以该前缀开头来有效地计算每个前缀的分数。

方法：

1. 将单词插入 Trie：

   • 我们将逐个字符地将每个单词插入到 Trie 中。
   • 在每个节点（代表一个字符），我们维护一个计数器来跟踪有多少单词通过该前缀。

2. 计算前缀分数：

   • 对于每个单词，当我们遍历 Trie 中的前缀时，我们将对每个节点存储的计数器求和，以计算每个前缀的分数。

3. 构建答案数组：

   • 对于每个单词，我们将计算其所有前缀的分数总和并将其存储在结果数组中。

让我们用 PHP 实现这个解决方案：2416。字符串前缀分数之和

<?php class TrieNode {
    /**
     * @var array
     */
    public $children;
    /**
     * @var int
     */
    public $count;

    public function __construct() {
        $this->children = [];
        $this->count = 0;
    }
}

class Trie {
    /**
     * @var TrieNode
     */
    private $root;

    public function __construct() {
        $this->root = new TrieNode();
    }

    /**
     * Insert a word into the Trie and update the prefix counts
     *
     * @param $word
     * @return void
     */
    public function insert($word) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }

    /**
     * Get the sum of prefix scores for a given word
     *
     * @param $word
     * @return int
     */
    public function getPrefixScores($word) {
       ...
       ...
       ...
       /**
        * go to ./solution.php
        */
    }
}

/**
 * @param String[] $words
 * @return Integer[]
 */
function sumOfPrefixScores($words) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$words1 = ["abc", "ab", "bc", "b"];
$words2 = ["abcd"];

print_r(sumOfPrefixScores($words1)); // Output: [5, 4, 3, 2]
print_r(sumOfPrefixScores($words2)); // Output: [4]
?>

解释：

1. TrieNode 类：

   • 每个节点都有一个子节点数组（代表单词中的下一个字符）和一个计数，用于跟踪有多少单词共享此前缀。

2. 特里类：

   • insert 方法向 Trie 中添加一个单词。当我们插入每个字符时，我们会增加每个节点的计数，表示有多少个单词具有此前缀。
   • getPrefixScores 方法计算给定单词的所有前缀的分数总和。它遍历 Trie，将单词中某个字符对应的每个节点的计数相加。

3. 主要函数（sumOfPrefixScores）：

   • First, we insert all words into the Trie.
   • Then, for each word, we calculate the sum of scores for its prefixes by querying the Trie and store the result in the result array.

Example:

For words = ["abc", "ab", "bc", "b"], the output will be:

Array
(
    [0] => 5
    [1] => 4
    [2] => 3
    [3] => 2
)

• "abc" has 3 prefixes: "a" (2 words), "ab" (2 words), "abc" (1 word) -> total = 5.
• "ab" has 2 prefixes: "a" (2 words), "ab" (2 words) -> total = 4.
• "bc" has 2 prefixes: "b" (2 words), "bc" (1 word) -> total = 3.
• "b" has 1 prefix: "b" (2 words) -> total = 2.

Time Complexity:

• Trie Construction: O(n * m) where n is the number of words and m is the average length of the words.
• Prefix Score Calculation: O(n * m) as we traverse each word's prefix in the Trie.

This approach ensures that we efficiently compute the prefix scores in linear time relative to the total number of characters in all words.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks ?. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub

以上是字符串前缀分数之和的详细内容。更多信息请关注PHP中文网其他相关文章！