Given a telephone number of variant digits, print all possible telephone words iteratively and recursively.void TelephoneWordsIterative(vector<int> num)
{
char *res = new char[num.size()];
// Initialize the result to the fist char or '-' for 0 and 1
for (int i = 0; i < num.size(); i++)
{
vector<char> chars = GetChars(num[i]);
if (chars.size() > 0)
res[i] = chars[0];
else
res[i] = '-';
}
while (true)
{
for (size_t i = 0; i < num.size(); i++)
if (res[i] != '-')
cout << res[i];
cout << endl;
for (int i = num.size() - 1; i >= -1; i--)
{
if (i == -1)
return;
vector<char> chars = GetChars(num[i]);
// Account for 0 and 1 and move on to next digit
if (chars.size() == 0)
res[i] = '-';
// If the last character, reset and move on to next digit
else if (res[i] == chars[chars.size() - 1])
res[i] = chars[0];
else if (res[i] == chars[0])
{
res[i] = chars[1];
break;
}
else if (res[i] == chars[1])
{
res[i] = chars[2];
break;
}
else if (chars.size() > 3 && res[i] == chars[2])
{
res[i] = chars[3];
break;
}
}
}
}
void TelephoneWordsRecursive(vector<int> num)
{
TelephoneWordsRecursiveHelper(num, 0);
}
void TelephoneWordsRecursiveHelper(vector<int> &num, size_t index)
{
// Static member will get instantiated only once
static char *res = new char[num.size()];
if (index == num.size())
{
for (size_t i = 0; i < num.size(); i++)
if (res[i] != '-')
cout << res[i];
cout << endl;
return;
}
vector<char> chars = GetChars(num[index]);
// For the case of number 0 and 1
if (0 == chars.size())
{
res[index] = '-';
return TelephoneWordsRecursiveHelper(num, index + 1);
}
for (char c : chars)
{
res[index] = c;
TelephoneWordsRecursiveHelper(num, index + 1);
}
}
vector<char> GetChars(int i)
{
vector<char> ret;
switch (i)
{
case 2:
ret.push_back('A');
ret.push_back('B');
ret.push_back('C');
break;
case 3:
ret.push_back('D');
ret.push_back('E');
ret.push_back('F');
break;
case 4:
ret.push_back('G');
ret.push_back('H');
ret.push_back('I');
break;
case 5:
ret.push_back('J');
ret.push_back('K');
ret.push_back('L');
break;
case 6:
ret.push_back('M');
ret.push_back('N');
ret.push_back('O');
break;
case 7:
ret.push_back('R');
ret.push_back('Q');
ret.push_back('S');
ret.push_back('T');
break;
case 8:
ret.push_back('T');
ret.push_back('U');
ret.push_back('V');
break;
case 9:
ret.push_back('W');
ret.push_back('X');
ret.push_back('Y');
ret.push_back('Z');
break;
}
return ret;
}
|