user3615045 user3615045 - 2 months ago 20
C++ Question

Letter combinations of a phone number

Given an digit string,we need to print all letter combinations the number represents

For input "23",output should be ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

class Solution {
public:
char ph[10][4]={{'0','0','0','0',},{'0','0','0','0',},{'a','b','c','0'},{'d','e','f','0'},{'g','h','i','0'},{'j','k','l','0'},{'m','n','o','0'},{'p','q','r','s'},{'t','u','v','0'},{'w','x','y','z'}};
vector<string> ans;
void print(string digits,string st,int pos)
{
int i,l=digits.size();
if(l==pos)
{
ans.push_back(st);
return;
}
else
{
for(i=pos;i<l;i++)
{
int ch=digits[i]-'0';
for(int j=0;j<4 && ph[ch][j]!='0';j++)
{
print(digits,st+ph[ch][j],i+1);
}
}

}
}
vector<string> letterCombinations(string digits) {
int l=digits.size();
if(!l)
return ans;
print(digits,"",0);
return ans;
}
};


But I get an error for input "22",which prints 'a','b',c' additionally.What is wrong with the code?

Answer

The problem is that you're both looping and recursing.

print("22", "", 0);

will recurse into

print("22", "a", 1);
print("22", "b", 1);
print("22", "c", 1);
print("22", "a", 2);
print("22", "b", 2);
print("22", "c", 2);

and your extra bits are the last three calls.

Get rid of the loop over the input digits (you're already doing that step by recursing):

 void print(string digits, string st, int pos)
 {
     if(digits.size() == pos)
     {
         ans.push_back(st);
     }
     else
     {
         int ch = digits[pos] - '0';
         for(int j = 0; j < 4 && ph[ch][j] != '0'; j++)
         {
             print(digits, st + ph[ch][j], pos + 1);
         }
     }
 }

(You also forgot to terminate some of your arrays, but that's a different issue.)

Comments