Rumah > Artikel > pembangunan bahagian belakang > Jumlah Skor Awalan Rentetan
2416. Jumlah Skor Awalan Rentetan
Kesukaran: Sukar
Topik: Tatasusunan, Rentetan, Percubaan, Pengiraan
Anda diberi susunan perkataan bersaiz n yang terdiri daripada rentetan bukan kosong.
Kami mentakrifkan skor perkataan rentetan sebagai nombor perkataan rentetan[i] sehingga perkataan ialah awalan perkataan[i].
Kembalikan jawapan tatasusunan saiz n dengan jawapan[i] ialah jumlah markah setiap tak kosong awalan perkataan[i].
Perhatikan bahawa rentetan dianggap sebagai awalan dirinya sendiri.
Contoh 1:
Contoh 2:
Kekangan:
Petunjuk:
Penyelesaian:
Kami boleh menggunakan struktur data Trie, yang sangat cekap untuk bekerja dengan awalan. Setiap nod dalam Trie akan mewakili huruf perkataan, dan kami akan mengekalkan pembilang pada setiap nod untuk menyimpan berapa kali awalan itu telah ditemui. Ini membolehkan kami mengira markah setiap awalan dengan cekap dengan mengira bilangan perkataan yang bermula dengan awalan itu.
Sisipkan Perkataan ke dalam Percubaan:
Kira Markah Awalan:
Bina Tatasusunan Jawapan:
Mari laksanakan penyelesaian ini dalam PHP: 2416. Jumlah Skor Awalan Rentetan
<?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> Penjelasan: </h3> <ol> <li> <p><strong>Kelas TrieNode:</strong></p> <ul> <li>Setiap nod mempunyai tatasusunan kanak-kanak (mewakili aksara seterusnya dalam perkataan) dan kiraan untuk menjejaki bilangan perkataan yang berkongsi awalan ini.</li> </ul> </li> <li> <p><strong>Kelas Percubaan:</strong></p> <ul> <li>Kaedah sisipan menambah perkataan pada Trie. Semasa kami memasukkan setiap aksara, kami menambah kiraan pada setiap nod, mewakili bilangan perkataan yang mempunyai awalan ini.</li> <li>Kaedah getPrefixScores mengira jumlah markah untuk semua awalan perkataan tertentu. Ia merentasi Trie, menjumlahkan kiraan setiap nod yang sepadan dengan aksara dalam perkataan.</li> </ul> </li> <li> <p><strong>Fungsi Utama (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:
Atas ialah kandungan terperinci Jumlah Skor Awalan Rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!