Find the number of possible lines of the alphabet from an array of numbers

Question

For line 12345 and the alphabet for matching numbers, for example a =1 , b =2 .., y=25 , z=26 ; write code to find the number of possible lines of the alphabet from a given line.

Ex line 12345 has possible alphabetical lines as {lcde,awde, abcde} from the mappings {12-3-4-5, 1-23-4-5, 1-2-3-4-5} .

I have a general idea of ​​how to do this. I guess this will be recursive. Look at the first digit and add the char mapping to the result, and then recurs with the help of an auxiliary array (1, size - 1). Also look at the first two digits and see if they are equal <= 26. If so, add this to the result and recursion (2, size - 2). Do this until the array of numbers becomes empty.

I'm still stuck in a real implementation. Is there a smarter way to do this than recursion?

Answer 1

This is similar to the Word Break Problem . You can use the same approach to solve it. You can use memoization to reduce the overall runtime. If you see in your example:

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

4 and 5 is repeated, and you calculate it again and again. You can save the permutation of a given index the first time you calculate, and use it later when you visit the same index.

pseudo code:

 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:

when you have a recursive call for index i , when you end up with this call (mostly returning from the current recursion), you have already used / computed / found all possible values ​​(all permutations for the substring starting at index i ). you can save these values ​​because if you see that there may be times when you again come to index i from some other index, say j (j<i) . so now this time you can return from this place instead of a more recursive call to index i , since you have already calculated the values ​​for index i , and this will be the same regardless of j

Answer 2

Just finish this coding, idea taken from @dream_machine

Basically, this is a backtracking algorithm, complexity is O (2n!). You need to track left to know if the line should output.

It seems that the algorithm is too slow, you may need to add a note to speed it up.

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

output

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