Anzahl der Möglichkeiten, bei einem gegebenen Wörterbuch eine Zielzeichenfolge zu bilden

1639. Anzahl der Möglichkeiten, eine Zielzeichenfolge anhand eines Wörterbuchs zu bilden

Schwierigkeit:Schwer

Themen:Array, String, dynamische Programmierung

Sie erhalten eine Liste von Zeichenfolgen mit Wörtern gleicher Länge und ein Zeichenfolgenziel.

Ihre Aufgabe besteht darin, mit den angegebenen Wörtern nach den folgenden Regeln ein Ziel zu bilden:

• Das Ziel sollte von links nach rechts gebildet werden.
• Um das i^te Zeichen (0-indiziert) des Ziels zu bilden, können Sie das k^te Zeichen des j^{ten Zeichenfolge in Wörtern, wenn Ziel[i] = Wörter[j][k].}
Sobald Sie das k
• te ^{Zeichen der j}ten ^{Wortfolge verwenden,} können Sie das xte ^{nicht mehr} verwenden Zeichen einer beliebigen Zeichenfolge in Wörtern, wobei x
• Wiederholen Sie den Vorgang, bis Sie das String-Ziel gebildet haben.

Beachten Sie, dass Sie mehrere Zeichen aus der gleichen Zeichenfolge in Wörtern verwenden können, sofern die oben genannten Bedingungen erfüllt sind.

Gib die Anzahl der Möglichkeiten zurück, aus Wörtern ein Ziel zu bilden. Da die Antwort möglicherweise zu groß ist, geben Sie sie modulo 10⁹ 7.

zurück

Beispiel 1:

• Eingabe: Wörter = ["acca", "bbbb", "caca"], Ziel = "aba"
• Ausgabe: 6
• Erklärung: Es gibt 6 Möglichkeiten, ein Ziel zu bilden.
  • "aba" -> Index 0 („acca“), Index 1 („bbbb“), Index 3 („caca“)
  • "aba" -> Index 0 („acca“), Index 2 („bbbb“), Index 3 („caca“)
  • "aba" -> Index 0 („acca“), Index 1 („bbbb“), Index 3 („acca“)
  • "aba" -> Index 0 („acca“), Index 2 („bbbb“), Index 3 („acca“)
  • "aba" -> Index 1 („caca“), Index 2 („bbbb“), Index 3 („acca“)
  • "aba" -> Index 1 („caca“), Index 2 („bbbb“), Index 3 („caca“)

Beispiel 2:

• Eingabe: Wörter = ["abba", "baab"], Ziel = "bab"
• Ausgabe: 4
• Erklärung: Es gibt 4 Möglichkeiten, ein Ziel zu bilden.
  • "bab" -> Index 0 („baab“), Index 1 („baab“), Index 2 („abba“)
  • "bab" -> Index 0 („baab“), Index 1 („baab“), Index 3 („baab“)
  • "bab" -> Index 0 („baab“), Index 2 („baab“), Index 3 („baab“)
  • "bab" -> Index 1 („abba“), Index 2 („baab“), Index 3 („baab“)

Einschränkungen:

• 1
• 1
• Alle Zeichenfolgen in Wörtern haben die gleiche Länge.
• 1
• Wörter[i] und Ziel enthalten nur englische Kleinbuchstaben.

Hinweis:

1. Speichern Sie für jeden Index i die Häufigkeit jedes Zeichens in der i^ten Zeile.
2. Verwenden Sie dynamische Programmierung, um die Anzahl der Möglichkeiten zum Erhalten der Zielzeichenfolge mithilfe des Frequenzarrays zu berechnen.

Lösung:

Das Problem besteht darin, die Anzahl der Möglichkeiten zur Bildung einer Zielzeichenfolge aus einem Wortwörterbuch zu ermitteln und dabei bestimmte Regeln zur Zeichenverwendung zu befolgen. Dies ist ein kombinatorisches Problem, das mithilfe von Dynamischer Programmierung (DP) und der Vorverarbeitung von Zeichenhäufigkeiten effizient gelöst werden kann.

Wichtige Punkte

1. Einschränkungen:
   • Wörter haben die gleiche Länge.
   • Zeichen in Wörtern können nur von links nach rechts verwendet werden.
2. Herausforderungen:
   • Effizientes Zählen der Möglichkeiten zur Zielbildung aufgrund großer Einschränkungen.
   • Vermeiden Sie Neuberechnungen durch Auswendiglernen.
3. Modulo:
   • Da das Ergebnis groß sein kann, werden alle Berechnungen Modulo 10⁹ 7.
   durchgeführt

Anfahrt

Die Lösung verwendet:

1. Vorverarbeitung:
   • Zählen Sie die Häufigkeit jedes Zeichens an jeder Position in allen Wörtern.
2. Dynamische Programmierung:
   • Verwenden Sie eine 2D-DP-Tabelle, um die Anzahl der Möglichkeiten zur Bildung der Zielzeichenfolge zu berechnen.

Schritte:

1. Wörter in ein Häufigkeitsarray vorverarbeiten (Anzahl).
2. Definieren Sie eine DP-Funktion, um mithilfe der vorverarbeiteten Zählungen rekursiv die Anzahl der Möglichkeiten zur Zielbildung zu ermitteln.

Planen

1. Eingabeanalyse:
   • Akzeptieren Sie Wörter und Ziele.
2. Vorverarbeitung:
   • Erstellen Sie ein counts-Array, in dem counts[j][char] die Häufigkeit von char an Position j in allen Wörtern darstellt.
3. Dynamische Programmierung:
   • Verwenden Sie eine rekursive Funktion mit Memoisierung, um die Anzahl der Möglichkeiten zur Bildung eines Ziels mithilfe von Zeichen aus gültigen Positionen in Wörtern zu berechnen.
4. Ergebnis zurückgeben:
   • Geben Sie die Gesamtzahl Modulo 10 zurück⁹7.

Lassen Sie uns diese Lösung in PHP implementieren: 1639. Anzahl der Möglichkeiten, eine Zielzeichenfolge anhand eines Wörterbuchs zu bilden

<?php const MOD = 1000000007;
/**
 * @param String[] $words
 * @param String $target
 * @return Integer
 */
function numWays($words, $target) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
 * Helper function for DP
 *
 * @param $i
 * @param $j
 * @param $counts
 * @param $target
 * @param $memo
 * @return float|int|mixed
 */
private function dp($i, $j, $counts, $target, &$memo) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example Usage
$words = ["acca", "bbbb", "caca"];
$target = "aba";
echo numWays($words, $target) . "\n"; // Output: 6

$words = ["abba", "baab"];
$target = "bab";
echo numWays($words, $target) . "\n"; // Output: 4
?>

Erläuterung:

1. Vorverarbeitungsschritt:

   • Erstellen Sie ein Zählarray:
     • Zählen Sie für jede Wortspalte die Vorkommen jedes Zeichens.
   • Beispiel: Wenn Wörter = ["acca", "bbbb", "caca"] sind, zählt für die erste Spalte[0] = {'a': 1, 'b': 1, 'c': 1 }.

2. Rekursiver DP:

   • Definieren Sie dp(i, j):
     • i ist der aktuelle Index im Ziel.
     • j ist die aktuelle Position in Worten.
   • Basisfälle:
     • Wenn i == len(target): Gesamtes Ziel gebildet → 1 zurückgeben.
     • Wenn j == len(words[0]): Keine weiteren Spalten zu verwenden → 0 zurückgeben.
   • Wiederholung:
     • Option 1: Verwenden Sie counts[j][target[i]] Zeichen ab Position j.
     • Option 2: Position j überspringen.

3. Optimierung:

   • Verwenden Sie eine Memoisierungstabelle, um Ergebnisse überlappender Teilprobleme zu speichern.

Beispiel-Anleitung

Eingabe:

Wörter = ["acca", "bbbb", "caca"], Ziel = "aba"

1. Vorverarbeitung:

   • counts[0] = {'a': 2, 'b': 0, 'c': 1}
   • counts[1] = {'a': 0, 'b': 3, 'c': 0}
   • counts[2] = {'a': 1, 'b': 0, 'c': 2}
   • counts[3] = {'a': 2, 'b': 0, 'c': 1}

2. DP-Berechnung:

   • dp(0, 0): Wie viele Möglichkeiten es gibt, um „aba“ beginnend mit Spalte 0 zu bilden.
   • Rekursive Berechnung unter Verwendung von Zählungen und Überspringen von Spalten.

Ausgabe: 6

Zeitkomplexität

1. Vorverarbeitung: O(n x m), wobei n die Anzahl der Wörter und m ihre Länge ist.
2. Dynamische Programmierung: O(l x m), wobei l die Länge des Ziels ist.
3. Gesamt: O(n x m l x m).

Ausgabe als Beispiel

• Eingabe: Wörter = ["acca", "bbbb", "caca"], Ziel = "aba"
• Ausgabe: 6

Dieses Problem ist ein großartiges Beispiel für die Kombination von Vorverarbeitung und dynamischer Programmierung, um eine kombinatorische Herausforderung effizient zu lösen.

Kontaktlinks

Wenn Sie diese Serie hilfreich fanden, denken Sie bitte darüber nach, dem Repository einen Stern auf GitHub zu geben oder den Beitrag in Ihren bevorzugten sozialen Netzwerken zu teilen? Ihre Unterstützung würde mir sehr viel bedeuten!

Wenn Sie weitere hilfreiche Inhalte wie diesen wünschen, folgen Sie mir gerne:

• LinkedIn
• GitHub

Das obige ist der detaillierte Inhalt vonAnzahl der Möglichkeiten, bei einem gegebenen Wörterbuch eine Zielzeichenfolge zu bilden. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!