從數陣列

Question

給定一個字符串12345和字母像a =1，b =2號碼映射查找可能的字母串號..，y=25，z=26;編寫代碼以查找給定字符串中可能的字母字符串的數量。

E.x.字符串12345從映射{12-3-4-5, 1-23-4-5, 1-2-3-4-5}有可能的字母字符串作爲{lcde,awde, abcde}。

我對如何做到這一點有一個總體的想法。我想它會是遞歸的。查看第一個數字並將它的char映射添加到結果中，然後使用子數組（1，size - 1）遞歸。再看看前兩位數字，看他們是否是< = 26.如果是這樣，將其添加到結果並遞歸（2，size - 2）。這樣做直到數組數組爲空。

雖然我陷入了實際的實施。有沒有比遞歸更聰明的方法嗎？

Answer 1

這類似於分詞問題。您可以使用相同的方法來解決它。您可以使用記憶來減少整體運行時間。如果你在給出的例子中看到：

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

4和5正在重複，你正在重複計算它。您可以在第一次計算時存儲給定索引的排列，並在以後每次訪問相同索引時使用它。

僞代碼：

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. 

詳細信息：

，當你有遞歸調用的發言權指數i，當你與此調用（從目前的遞歸基本恢復）做你有已經使用/計算/找到了所有可能的值（從索引i開始的子串的全部排列）。您可以存儲這些值，因爲如果您會看到有些時候您可能會再次從其他索引索引i。所以現在這個時候你可以從這個地方本身，而不是更多的遞歸調用索引i返回因爲你已經計算出的值指數i，這將是j

Answer 2

相同，不論剛做完這個編碼，想法是從@dream_machine

基本上它是一個回溯算法，複雜度爲O（2n！）， 需要跟蹤left知道應該把字符串輸出。

似乎算法太慢，也許需要添加一些備忘錄來加速它。

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; 
    } 
} 

輸出

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