Geben Sie eine codierte Nachricht an, und zählen Sie die Anzahl der Möglichkeiten, wie diese entschlüsselt werden kann

Question

Geben Sie eine codierte Nachricht an, und zählen Sie die Anzahl der Möglichkeiten, wie diese entschlüsselt werden kann

8

Sie erhalten eine verschlüsselte Nachricht, die nur Zahlen enthält. Sie erhalten auch das folgende Mapping

%Vor%

Geben Sie eine codierte Nachricht an, und zählen Sie die Anzahl der Möglichkeiten, wie sie dekodiert werden kann.

zB: 12 kann auf zwei Arten dekodiert werden: (A, B) und (L)

Ich habe den Algorithmus gefunden, die Zahlen als Zeichenkette zu akzeptieren und dann nach jeder Ziffer zu suchen:

%Vor%

Jedes Mal, wenn ich versuche, die erste Ziffer in der Nachricht zu einem Buchstaben zu kodieren, oder ich kann die ersten zwei Ziffern, wenn möglich, in einen Buchstaben kodieren. Wenn es keine Möglichkeit gibt, zu codieren, als würde man auf eine einzelne "0" treffen oder auf "32" stoßen, dann einfach zurückgeben.

Kann dieses Problem effizienter gelöst werden?

algorithm string c

poorvankBhatia 23.03.2013, 11:10

quelle

2 Antworten

0

Rekursive Lösung

%Vor%

Beispiel kehrt zurück

Zählcodes ("123"); // gibt 3
Zählcodes ("1230"); // gibt 0 zurück
Zählcodes ("1220"); // gibt 2
Zählcodes ("12321"); // gibt 6

user93353 23.03.2013 11:32

quelle

Tags und Links algorithm string c

Django: Verwenden von Annotate, Count und Distinct in einem Queryset Libtool-Bibliothek verwendet, aber 'LIBTOOL' ist nicht definiert?

score 13 · Accepted Answer

Ihre aktuelle Annäherung an das Problem ist korrekt. Obwohl, Sie müssen wirklich vorsichtig sein, dass Sie alle Fälle behandeln, die es nicht klar ist, und das wird meine Antwort ein bisschen länger als nötig machen.

Eine korrekte Methode, dieses Problem zu sehen, ist eine dynamische Programmierung Perspektive. Betrachten wir Ihre Eingabe als message und ihre Länge als n .

Um ein message von n Zeichen zu dekodieren, müssen Sie wissen, auf wie viele Arten Sie message mit n - 1 Zeichen und ein message mit n - 2 Zeichen dekodieren können. Das heißt,

Eine Nachricht von n Zeichen.

%Vor%

Verwenden einer 1-stelligen und einer message von n - 1 Zeichen lang.

%Vor%

Verwenden Sie eine 2-stellige und eine message von n - 2 Zeichen lang.

%Vor%

Nun können Sie sich fragen:

Wie berechne ich, auf wie viele Arten Sie message von n - 1 Zeichen und von n - 2 Zeichen dekodieren können?

Es ist eigentlich genauso. Schließlich werden Sie es auf seinen Basisfall reduzieren.

Sagen wir ways[n] ist die Anzahl der Möglichkeiten, wie Sie message von n Zeichen dekodieren können. Dann können Sie ways[n] auf diese Weise setzen,

%Vor%

(Da es keine Ahnung gibt, wie Sie die Anzahl der Möglichkeiten für eine leere Zeichenkette definieren würden, betrachtete ich das als 1 .)

Mit geeigneten Einschränkungen und dem Basisfall

n = 0 ,
%Vor%
n > 1 und message[n] ist gültig und message[n - 1:n] ist gültig,
%Vor%
n > 1 und message[n] ist gültig und message[n - 1:n] ist nicht gültig,
%Vor%
n > 1 und message[n] ist nicht gültig und message[n - 1:n] ist gültig,
%Vor%
andernfalls
%Vor%

Eine iterative decode Funktion in C kann wie folgt aussehen,

%Vor%

Sie können es hier bei ideone sehen. Ich verwende konstanten zusätzlichen Speicher für die Berechnung.