ホームページ >バックエンド開発 >PHPチュートリアル >文字列のプレフィックススコアの合計
2416. Summe der Präfixwerte der Zeichenfolgen
Schwierigkeit:Schwer
Themen:Array, String, Trie, Counting
Sie erhalten ein Array von Wörtern der Größe n, bestehend aus nicht leeren Zeichenfolgen.
Wir definieren die Punktzahl eines Zeichenfolgenworts als die Anzahl der Zeichenfolgenwörter[i], sodass das Wort ein Präfix der Wörter[i] ist.
Gib eine Array-Antwort der Größe n zurück, wobei Antwort[i] die Summe der Bewertungen aller nicht leeren Präfixe von Wörtern[i] ist.
Beachten Sie, dass eine Zeichenfolge als Präfix von sich selbst betrachtet wird.
Beispiel 1:
Beispiel 2:
Einschränkungen:
Hinweis:
Lösung:
Wir können eine Trie-Datenstruktur verwenden, die besonders effizient für die Arbeit mit Präfixen ist. Jeder Knoten im Trie stellt einen Buchstaben des Wortes dar, und wir verwalten an jedem Knoten einen Zähler, um zu speichern, wie oft dieses Präfix angetroffen wurde. Dadurch können wir die Punktzahl jedes Präfixes effizient berechnen, indem wir zählen, wie viele Wörter mit diesem Präfix beginnen.
Wörter in Trie einfügen:
Präfix-Scores berechnen:
Antwortarray erstellen:
Lassen Sie uns diese Lösung in PHP implementieren: 2416. Summe der Präfixwerte der Zeichenfolgen
<?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] ?> <h3> Erläuterung: </h3> <ol> <li> <p><strong>TrieNode-Klasse:</strong></p> <ul> <li>Jeder Knoten verfügt über ein Array von untergeordneten Knoten (die die nächsten Zeichen im Wort darstellen) und eine Zählung, um zu verfolgen, wie viele Wörter dieses Präfix teilen.</li> </ul> </li> <li> <p><strong>Trie-Klasse:</strong></p> <ul> <li>Die Einfügemethode fügt dem Trie ein Wort hinzu. Wenn wir jedes Zeichen einfügen, erhöhen wir die Anzahl an jedem Knoten und geben an, wie viele Wörter dieses Präfix haben.</li> <li>Die getPrefixScores-Methode berechnet die Summe der Bewertungen für alle Präfixe eines bestimmten Wortes. Es durchläuft den Trie und addiert die Anzahl jedes Knotens, der einem Zeichen im Wort entspricht.</li> </ul> </li> <li> <p><strong>Hauptfunktion (sumOfPrefixScores):</strong></p> <ul> <li>First, we insert all words into the Trie.</li> <li>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.</li> </ul> </li> </ol> <h3> Example: </h3> <p>For words = ["abc", "ab", "bc", "b"], the output will be:<br> </p> <pre class="brush:php;toolbar:false">Array ( [0] => 5 [1] => 4 [2] => 3 [3] => 2 )
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:
以上が文字列のプレフィックススコアの合計の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。