Count möglich Dekodierungen einer bestimmten Ziffernfolge

Question

Angenommen, wir haben eine Reihe von Binärwerten in der einige Teile auf bestimmte Buchstaben entsprechen kann, zum Beispiel:

A = 0 
B = 10 
C = 001 
D = 010 
E = 001 

Zum Beispiel, wenn wir die Zeichenfolge „001010 nehmen ", wir können 6 verschiedene Möglichkeiten haben:

AABB 
ADB 
CAB 
CD 
EAB 
ED 

Ich muss die genaue Anzahl der Kombinationen extrahieren.
Ich versuche, das Problem konzeptionell durch eine dynamische Programmierung Sicht zu lösen, aber ich habe Schwierigkeiten bei der Formulierung von Teilproblemen und in der Zusammensetzung der entsprechenden Matrix.
Ich schätze alle Hinweise auf die richtige Algorithmusformulierung.
Vielen Dank im Voraus.

Answer 1

Sie können einen DP formulieren wobei f(i) = sum(f(i - j) * count(matches_j)), for all matches of length j ending at index i, die am Eingang abhängig, können Sie auch durch das Erstellen eines benutzerdefinierten trie für das Wörterbuch beschleunigen, so dass Sie nur relevante Ergebnisse (zB prüfen würde, A gefolgt von B gefolgt von D). So nehmen Sie Ihr Beispiel:

f(0) = 1 
f(1) = 1 * f(0) = 1 
f(2) = 2 
f(3) = 1 * f(2) + 1 * f(1) + 1 * f(0) = 4 
f(4) = 0 
f(5) = 1 * f(4) + 1 * f(3) + 1 * f(2) = 6 

Answer 2

Bei der Lösung von DP-Problemen hilft es oft, zuerst über eine rekursive Lösung nachzudenken und dann über eine Konvertierung in eine DP-Lösung nachzudenken.

Eine nette rekursive Erkenntnis hier ist, dass, wenn Sie eine nichtleere Ziffernfolge haben, jede Art der Dekodierung mit einem einzelnen Zeichen beginnt. Man könnte daher die Anzahl der Möglichkeiten zum Decodieren der Zeichenkette zählen, indem man jedes Zeichen ausprobiert, um zu sehen, ob es am Anfang übereinstimmt, und wenn ja, wie viele Wege es gibt, den Rest der Zeichenkette zu dekodieren.

Der Grund, warum dies zu einem schönen DP-Problem wird ist, dass wenn Sie ein einzelnes Zeichen abziehen, Sie mit einer kürzeren Folge von Ziffern bleiben, die immer ein Suffix der ursprünglichen Zeichenfolge ist. Stellen Sie sich vor, Sie hätten eine Tabelle erstellt, die für jedes Suffix der ursprünglichen Zeichenkette speichert, wie viele Möglichkeiten es gibt, diese Zeichenkette zu dekodieren. Wenn Sie diese Matrix von rechts nach links mit der obigen Erkenntnis ausfüllen, erhalten Sie schließlich die endgültige Antwort, indem Sie den Eintrag für die gesamte Zeichenfolge lesen.

Sehen Sie, wenn Sie einen Weg finden, um dies in einen konkreten Algorithmus umzuwandeln und dann zu gehen und es zu kodieren. Viel Glück!

Answer 3

Sie können eine einfache rekursive Prozedur verwenden: versuchen Sie, jedes Muster an den Anfang der Zeichenfolge anzupassen; Wenn es eine Übereinstimmung gibt, wiederholen Sie rekursiv mit dem Rest der Zeichenfolge. Wenn die Zeichenfolge leer ist, haben Sie eine Decodierung gefunden.

Patterns= ["0", "10", "001", "010", "001"] 
Letters= "ABCDE" 

def Decode(In, Out): 
    global Patterns 

    if len(In) == 0: 
     print Out 
    else: 
     for i in range(len(Patterns)): 
      if In[:len(Patterns[i])] == Patterns[i]: 
       Decode(In[len(Patterns[i]):], Out + Letters[i]) 

Decode("001010", "") 

AABB 
ADB 
CAB 
CD 
EAB 
ED