Given a phone number and compute all the combinations of the words/letters mapped into the phone number.
For instance: phone number 23 and the combinations will be
AD
AE
AF
BD
BE
BF
CD
CE
CF
Of course based on the mapping, the valid numbers will be from 2 to 9
2. Problem analysis and solution
Given a phone number with n digits. The number combination will be bounded as [3^n, 4^n]. Given a value of n as 10, the number of combinations will be around 1 million. If n as 20, it could be very huge - trillions - 4^20 - 2^40.
In order to solve this problem we can adopt dynamic programming. Its key is to find the sub problem. Given a phone number with n digits, we represent its combination as f(DnDn-1...D3D2D1, n). The combination can be represent as:
f(DnDn-1...D1, n) = LETTERn + f(Dn-1...D1, n-1)
Subject LETTERn is any letter choice of this number, for instance (P, Q, R, S) for number 7.
Miscrosoft Visual C++ 2010 Express
*********************************************************************************
#include "stdafx.h"
#include <string>
#include <vector>
std::vector<std::vector<std::string> > MapDigToLetter;
void ConstructMapDigToLetter(std::vector<std::vector<std::string> >& mdl)
{
{ // 2
std::vector<std::string> noMap;
noMap.push_back("A");
noMap.push_back("B");
noMap.push_back("C");
mdl.push_back(noMap);
}
{ // 3
std::vector<std::string> noMap;
noMap.push_back("D");
noMap.push_back("E");
noMap.push_back("F");
mdl.push_back(noMap);
}
{ // 4
std::vector<std::string> noMap;
noMap.push_back("G");
noMap.push_back("H");
noMap.push_back("I");
mdl.push_back(noMap);
}
{ // 5
std::vector<std::string> noMap;
noMap.push_back("J");
noMap.push_back("K");
noMap.push_back("L");
mdl.push_back(noMap);
}
{ // 6
std::vector<std::string> noMap;
noMap.push_back("M");
noMap.push_back("N");
noMap.push_back("O");
mdl.push_back(noMap);
}
{ // 7
std::vector<std::string> noMap;
noMap.push_back("P");
noMap.push_back("Q");
noMap.push_back("R");
noMap.push_back("S");
mdl.push_back(noMap);
}
{ // 8
std::vector<std::string> noMap;
noMap.push_back("T");
noMap.push_back("U");
noMap.push_back("V");
mdl.push_back(noMap);
}
{ //9
std::vector<std::string> noMap;
noMap.push_back("W");
noMap.push_back("X");
noMap.push_back("Y");
noMap.push_back("Z");
mdl.push_back(noMap);
}
}
void GetCombinationsOfLettersBasedOnNumbers(
const std::vector<unsigned char>& phoneNumber,
size_t index,
std::string& words,
std::string& letters)
{
if (index == phoneNumber.size()) {
words.append(letters);
words.append(";");
return;
}
unsigned char number = phoneNumber[index];
std::vector<std::string>& curMap= MapDigToLetter[number - 2];
for (unsigned size_t i = 0; i < curMap.size(); ++i) {
std::string copyLetters(letters);
copyLetters.append(curMap[i]);
GetCombinationsOfLettersBasedOnNumbers(phoneNumber,
index+1,
words,
copyLetters);
}
}
int _tmain(int argc, _TCHAR* argv[])
{
ConstructMapDigToLetter(MapDigToLetter);
std::vector<unsigned char> phoneNumber;
phoneNumber.push_back(2);
phoneNumber.push_back(2);
phoneNumber.push_back(3);
std::string words, letters;
GetCombinationsOfLettersBasedOnNumbers(phoneNumber, 0, words, letters);
return 0;
}
3. Solution analysis
Given a phone number with n digits that composed of only digits 2-9. we are only considering GetCombinationsOfLettersBasedOnNumbers().
Recursion stack depth: O(n) and this algorithm does the depth first.
Memory usage: This algorithm does the depth first. f(n), f(n-1), ......, f(1), f(0) will each have its own copy of the automatic variables. f(0) is the special case and it will hit "return" before declaring the local variables. Hence it memory usage will be:
n times <unsigned char number>
n times <std::vector<std::string>& curMap>
n times <unsigned size_t i>
n times <std::string copyLetters>
It is worth pointing out that size of <std::string copyLetters> will be like:
f(n) -------- has a string with size of 0
f(n-1) ------ has a string with size of 1
......
f(1) -------- has a string with size of n-1
So in totally <std::string copyLetters> will take sum(0, 1, ......, n-1) = n*(n-1)/2; Hence the memory usage will be O(n^2).
Cache the search path locally:
For each f(m) has to remember the search depth so far it has gone through. The search path has to be cached locally from f(n), f(n-1), ...., f(m+1), f(m). And for each f(m), because the m-th number has difference choices of letters, which is enumerated in the for loop, the search depth for f(m) will be the choices of letters so far,
LETTERn, LETTERn-1, ..., LETTERm+1
And for f(m-1) will be
LETTERn, LETTERn-1, ..., LETTERm+1, LETTERm
Here is the example: given a phone number 23456789
Now are on number 6 - f(4), assuming that we have search stack path as
B,F,G,K, (with B-2, F-3, G-4, K-5)
Then, f(4)'s sub-problem, 7 - f(3) search stack could be (7 follows 6 in the above phone number)
B,F,G,K,M
B,F,G,K,N
B,F,G,K,O
"std::string copyLetters(letters);" has to be declared in the for loop to make sure the search stack depth updated correctly and accordingly. It copies the search stack it already has gone through, which is f(4) in this example, appends any choice of number 6 (M, N, O) and then passes to its sub-problem, f(3), by the recursive function calling.
[1] http://wcipeg.com/problem/ccc06j3
No comments:
Post a Comment