Beispielcode-Analyse für die Dekodierungsmethode des Go-Java-Algorithmus

Dekodierungsmethode

Eine Nachricht, die die Buchstaben A-Z enthält, wird mit der folgenden Zuordnung kodiert:

• 'A' -> "1"

• 'B' -> "2"

• . .

• 'Z' -> "26"

Um die codierte Nachricht zu dekodieren, müssen alle Zahlen basierend auf der oben abgebildeten Methode wieder Buchstaben zugeordnet werden (es kann mehrere Methoden geben). Beispielsweise kann „11106“ zugeordnet werden zu:

„AAJF“, gruppieren Sie die Nachricht als (1 1 10 6)

„KJF“, gruppieren Sie die Nachricht als (11 10 6)

Beachten Sie, dass die Nachricht nicht sein kann gruppiert als (1 11 06), da „06“ nicht auf „F“ abgebildet werden kann, da „6“ und „06“ in der Zuordnung nicht gleichwertig sind.

Angenommen, Sie haben eine nicht leere Zeichenfolge, die nur Zahlen enthält, berechnen Sie bitte die Gesamtzahl der Dekodierungsmethoden und geben Sie sie zurück.

Die Fragedaten garantieren, dass die Antwort eine 32-Bit-Ganzzahl sein muss.

• Beispiel 1:

Eingabe: s = „12“

Ausgabe: 2

Erläuterung: Es kann als „AB“ (1 2) oder „L“ (12) dekodiert werden.

• Beispiel 2:

Eingabe: s = „226“

Ausgabe: 3

Erklärung: Es kann als „BZ“ (2 26), „VF“ (22 6), oder „BBF“ (2 2 6).

• Beispiel 3:

Eingabe: s = „0“

Ausgabe: 0

Erklärung: Zahlen, die mit 0 beginnen, sind keine Zeichen zugeordnet.

Gültige Zuordnungen mit 0 sind „J“ ->

Da es keine Zeichen gibt, gibt es keine effiziente Möglichkeit, dies zu entschlüsseln, da alle Zahlen zugeordnet werden müssen.

Tipp:

1 <= s.length <= 100

s enthalten nur Zahlen und können führende Nullen enthalten.

Methode 1: Dynamische Programmierung (Java)

Für eine gegebene Zeichenfolge s sei ihre Länge n und die darin enthaltenen Zeichen von links nach rechts seien s[1], s[2],..., s[ N]. Mithilfe der dynamischen Programmierung können wir die Anzahl der Dekodierungsmethoden für eine Zeichenfolge berechnen.

Konkret sei fi die Anzahl der Dekodierungsmethoden für die ersten i Zeichen s[1..i] der Zeichenfolge s. Bei der Zustandsübertragung können wir berücksichtigen, welche Zeichen in s für die letzte Dekodierung verwendet wurden )

Spezifische Methodenideen finden Sie in der obigen Beschreibung. Durch die Verwendung temporärer Variablen wird die Raumkomplexität von o(n) auf o(1) reduziert.

class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            if (s.charAt(i - 1) != &#39;0&#39;) {
                f[i] += f[i - 1];
            }
            if (i > 1 && s.charAt(i - 2) != &#39;0&#39; && ((s.charAt(i - 2) - &#39;0&#39;) * 10 + (s.charAt(i - 1) - &#39;0&#39;) <= 26)) {
                f[i] += f[i - 2];
            }
        }
        return f[n];
    }
}

Zeitkomplexität: o(n)

Raumkomplexität: o(1)

Das obige ist der detaillierte Inhalt vonBeispielcode-Analyse für die Dekodierungsmethode des Go-Java-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!