字串前綴分數之和

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中文網其他相關文章！