Suche Anzahl der möglichen Alphabet Strings von Number Array

Question

einen String 12345 und ein Alphabet zu number mapping wie a =1 gegeben, b =2 .., y=25, z=26; Schreibe einen Code, um die Anzahl der möglichen Buchstabenfolgen aus der angegebenen Zeichenfolge zu finden.

E.x. Die Zeichenfolge 12345 kann alphabetische Zeichenfolgen wie {lcde,awde, abcde} aus den Zuordnungen {12-3-4-5, 1-23-4-5, 1-2-3-4-5} enthalten.

Ich habe eine allgemeine Vorstellung davon, wie es geht. Ich stelle mir vor, es wäre rekursiv. Sehen Sie sich die erste Ziffer an und fügen Sie ihr Char-Mapping zum Ergebnis hinzu und suchen Sie dann mit dem Sub-Array (1, size - 1). Schauen Sie sich auch die zwei ersten Ziffern an und sehen Sie, ob sie < = 26 sind. Falls ja, fügen Sie das dem Ergebnis hinzu und rekurven Sie (2, size - 2). Tun Sie dies, bis das Zahlenfeld leer ist.

Ich bleibe jedoch auf der tatsächlichen Implementierung stecken. Gibt es einen klügeren Weg als Rekursion?

Answer 1

Dies ist ähnlich wie Word Break Problem. Sie können denselben Ansatz verwenden, um es zu lösen. Sie können Memoization verwenden, um die Gesamtlaufzeit zu reduzieren. Wenn Sie in Ihrem gegebenen Beispiel sehen:

12-3-4-5, 1-23-4-5, 1-2-3-4-5 

4 und 5 wird wiederholt und Sie berechnen es immer wieder. Sie können die Permutation eines bestimmten Index zum ersten Mal speichern und später verwenden, wenn Sie denselben Index aufrufen.

Pseudocode:

recursive_function(string,index) 
if you have already calculated values for this index in previous call 
    return value 

recursive_function(string,index+1) 
if possible 
    recursive_function(string,index+2) 

store this value for future use. 

Detail:

wenn Sie rekursiven Aufruf für etwa Index i haben, wenn Sie mit diesem Anruf fertig sind (im Wesentlichen aus dem laufenden Rekursion Rückkehr) Sie haben bereits verwendet/berechnet/alle möglichen Werte gefunden (alle Permutationen für Teilstrings ab Index i). Sie können diese Werte speichern, denn wenn Sie sehen, dass es Zeiten geben kann, in denen Sie wieder kommen werden, um i von einem anderen Index zu sagen, sagen Sie j (j<i). so jetzt diese Zeit kann man von diesem Ort zurückkehrt selbst statt mehr rekursiven Aufruf für Index i wie Sie bereits Werte für den Index i berechnet haben, und das wird gleich, unabhängig von j

Answer 2

einfach diese Codierung beenden sein, Idee ist von @dream_machine

Grundsätzlich ist es ein Backtracking-Algorithmus, Komplexität ist O (2n!), Need behalten die left zu wissen, sollte String zur Ausgabe setzen.

Scheint der Algorithmus ist zu langsam, vielleicht müssen Sie etwas Memo hinzufügen, um es zu beschleunigen.

void helper(int start, string &s, string &path, vector<string> &result, int); 

vector<string> 
getPossibleCombo(string &s) { 
    vector<string> result; 
    string path; 
    helper(0, s, path, result, s.size()); 
    return result; 
} 

void helper(int start, string &s, string &path, vector<string> &result, int left) { 
    if (start == s.size() && left == 0) { 
     result.push_back(path); 
     return; 
    } 

    for (int i = start; i < s.size(); i++) { 
     path.push_back('a' + (s[i] - '0') - 1); 
     helper(i + 1, s, path, result, left - 1); 
     path.pop_back(); 

     if (i < s.size() - 1 && s[i] > '0' && s[i] <= '2') { // can try two. 
      if (s[i] == '2' && s[i+1] > '6') 
       continue; 
      int c = (s[i] - '0') * 10 + s[i + 1] - '0'; 
      path.push_back('a' + c - 1); 
      helper(i + 2, s, path, result, left - 2); 
      path.pop_back(); 
     } 
    } 
} 

int main() { 
    string s("12345"); 
    auto r = getPossibleCombo(s); 
    for (auto &s : r) { 
     cout << s << endl; 
    } 
} 

Ausgang ist

bash-3.2$ g++ -std=c++11 -g test2.cpp && ./a.out 
abcde 
awde 
lcde