文字列のプレフィックススコアの合計

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.

• Wenn beispielsweise Wörter = ["a", "ab", "abc", "cab"] sind, beträgt die Punktzahl von "ab" 2, da "ab" ein Präfix von "ab" und "ab" ist „abc“.

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:

• Eingabe: Wörter = ["abc", "ab", "bc", "b"]
• Ausgabe: [5,4,3,2]
• Erklärung: Die Antwort für jede Zeichenfolge lautet wie folgt:
  • „abc“ hat drei Präfixe: „a“, „ab“ und „abc“.
  • Es gibt 2 Zeichenfolgen mit dem Präfix „a“, 2 Zeichenfolgen mit dem Präfix „ab“ und 1 Zeichenfolge mit dem Präfix „abc“.
  • Die Summe ist Antwort[0] = 2 + 2 + 1 = 5.
  • „ab“ hat zwei Präfixe: „a“ und „ab“.
  • Es gibt 2 Zeichenfolgen mit dem Präfix „a“ und 2 Zeichenfolgen mit dem Präfix „ab“.
  • Die Summe ist Antwort[1] = 2 + 2 = 4.
  • „bc“ hat zwei Präfixe: „b“ und „bc“.
  • Es gibt 2 Zeichenfolgen mit dem Präfix „b“ und 1 Zeichenfolge mit dem Präfix „bc“.
  • Die Summe ist Antwort[2] = 2 + 1 = 3.
  • „b“ hat 1 Präfix: „b“.
  • Es gibt 2 Zeichenfolgen mit dem Präfix „b“.
  • Die Summe ist Antwort[3] = 2.

Beispiel 2:

• Eingabe:words = ["abcd"]
• Ausgabe: [4]
• Erklärung:
  • „abcd“ hat 4 Präfixe: „a“, „ab“, „abc“ und „abcd“.
  • Jedes Präfix hat eine Punktzahl von eins, daher ist die Gesamtsumme Antwort[0] = 1 + 1 + 1 + 1 = 4.

Einschränkungen:

• 1
• 1
• Wörter[i] bestehen aus englischen Kleinbuchstaben.

Hinweis:

1. Mit welcher Datenstruktur können Sie die Punktzahl jedes Präfixes effizient verfolgen?
2. Verwenden Sie einen Versuch. Fügen Sie alle Wörter ein und bewahren Sie an jedem Knoten einen Zähler auf, der Ihnen anzeigt, wie oft wir jedes Präfix besucht haben.

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.

Ansatz:

1. Wörter in Trie einfügen:

   • Wir fügen jedes Wort Zeichen für Zeichen in das Trie ein.
   • An jedem Knoten (der ein Zeichen darstellt) verwalten wir einen Zähler, der verfolgt, wie viele Wörter dieses Präfix durchlaufen.

2. Präfix-Scores berechnen:

   • Für jedes Wort summieren wir beim Durchlaufen seiner Präfixe im Trie die an jedem Knoten gespeicherten Zähler, um die Punktzahl für jedes Präfix zu berechnen.

3. Antwortarray erstellen:

   • Für jedes Wort berechnen wir die Summe der Bewertungen für alle seine Präfixe und speichern sie im Ergebnisarray.

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

Erläuterung:

1. TrieNode-Klasse:

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

2. Trie-Klasse:

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

3. Hauptfunktion (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 中国語 Web サイトの他の関連記事を参照してください。