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].

• Sebagai contoh, jika perkataan = ["a", "ab", "abc", "cab"], maka skor "ab" ialah 2, kerana "ab" ialah awalan bagi kedua-dua "ab" dan "abc".

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:

• Input: perkataan = ["abc","ab","bc","b"]
• Output: [5,4,3,2]
• Penjelasan: Jawapan untuk setiap rentetan adalah seperti berikut:
  • "abc" mempunyai 3 awalan: "a", "ab" dan "abc".
  • Terdapat 2 rentetan dengan awalan "a", 2 rentetan dengan awalan "ab", dan 1 rentetan dengan awalan "abc".
  • Jumlahnya ialah jawapan[0] = 2 + 2 + 1 = 5.
  • "ab" mempunyai 2 awalan: "a" dan "ab".
  • Terdapat 2 rentetan dengan awalan "a", dan 2 rentetan dengan awalan "ab".
  • Jumlahnya ialah jawapan[1] = 2 + 2 = 4.
  • "bc" mempunyai 2 awalan: "b" dan "bc".
  • Terdapat 2 rentetan dengan awalan "b", dan 1 rentetan dengan awalan "bc".
  • Jumlahnya ialah jawapan[2] = 2 + 1 = 3.
  • "b" mempunyai 1 awalan: "b".
  • Terdapat 2 rentetan dengan awalan "b".
  • Jumlahnya ialah jawapan[3] = 2.

Contoh 2:

• Input: perkataan = ["abcd"]
• Output: [4]
• Penjelasan:
  • "abcd" mempunyai 4 awalan: "a", "ab", "abc" dan "abcd".
  • Setiap awalan mempunyai skor satu, jadi jumlahnya ialah jawapan[0] = 1 + 1 + 1 + 1 = 4.

Kekangan:

• 1
• 1
• perkataan[i] terdiri daripada huruf kecil Inggeris.

Petunjuk:

1. Apakah struktur data yang akan membolehkan anda menjejaki markah setiap awalan dengan cekap?
2. Gunakan Cubaan. Masukkan semua perkataan ke dalamnya dan simpan pembilang pada setiap nod yang akan memberitahu anda berapa kali kami telah melawat setiap awalan.

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.

Pendekatan:

1. Sisipkan Perkataan ke dalam Percubaan:

   • Kami akan memasukkan setiap perkataan ke dalam aksara Trie mengikut aksara.
   • Pada setiap nod (mewakili aksara), kami mengekalkan pembilang yang menjejaki bilangan perkataan yang melalui awalan itu.

2. Kira Markah Awalan:

   • Untuk setiap perkataan, semasa kami melintasi awalannya dalam Trie, kami akan menjumlahkan pembilang yang disimpan pada setiap nod untuk mengira skor bagi setiap awalan.

3. Bina Tatasusunan Jawapan:

   • Untuk setiap perkataan, kami akan mengira jumlah markah untuk semua awalannya dan menyimpannya dalam tatasusunan hasil.

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]
?>

Penjelasan:

1. Kelas TrieNode:

   • Setiap nod mempunyai tatasusunan kanak-kanak (mewakili aksara seterusnya dalam perkataan) dan kiraan untuk menjejaki bilangan perkataan yang berkongsi awalan ini.

2. Kelas Percubaan:

   • Kaedah sisipan menambah perkataan pada Trie. Semasa kami memasukkan setiap aksara, kami menambah kiraan pada setiap nod, mewakili bilangan perkataan yang mempunyai awalan ini.
   • Kaedah getPrefixScores mengira jumlah markah untuk semua awalan perkataan tertentu. Ia merentasi Trie, menjumlahkan kiraan setiap nod yang sepadan dengan aksara dalam perkataan.

3. Fungsi Utama (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

Atas ialah kandungan terperinci Jumlah Skor Awalan Rentetan. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!