Interview Question
Country: United States
DP formula:
if s[i] == 0, dp[i] = 0
else if s[i] <= 2 && s[i+1] <= 6, dp[i] = dp[i+1] + dp[i+2]
else dp[i] = dp[i+1]
Code in C++:
int getWaysToDecode(const string& text){
//check if head decodable
if(text.empty() || text[0] == '0') return 0;
//if single character
if(text.size() == 1) return 1;
int len = text.size(), i;
int* dp = new int[len + 1];
//check if memory allocation failed
if(dp == NULL) return -1;
dp[len] = 1;
dp[len-1] = text[len-1] > '0';
for(i = len-2; i >= 0; --i){
if(text[i] > '0'){
//we can decode text[i] as a one-code word
dp[i] = dp[i+1];
//try to decode text[i,i+1] as a two-code word
if(text[i] <= '2' && text[i+1] <= '6') dp[i] += dp[i+2];
}
else dp[i] = 0;
}
//free memory before return
len = dp[0];
delete[] dp;
return len;
}
1, Check the last two digits before the letter. Add all the possible array to a stack.
2, Poll one item from the stack and repeat step 1.
3, If the pulled item has no letter, put it in the result.
if you need print the letters
void decode(const char* number, char* letters, int n, int idxN = 0, int idxL = 0)
{
if (idxN == n)
{
printf("%s\n", letters);
return;
}
if (number[idxN] != '0')
{
letters[idxL] = number[idxN] - '0' - 1 + 'a';
letters[idxL + 1] = '\0';
decode(number, letters, n, idxN+1, idxL + 1);
}
if (idxN+1 < n && (number[idxN]-'0')*10 + number[idxN+1]-'0' <= 26)
{
letters[idxL] = (number[idxN]-'0')*10 + number[idxN+1]-'0' - 1 + 'a';
letters[idxL + 1] = '\0';
decode(number, letters, n, idxN+2, idxL + 1);
}
}
if not, use memorization to avoid recompute the same solutions again
int count(const char* number, int* numWays, int n, int idxN)
{
if (idxN == n)
{
return 1;
}
else if (idxN > n) return 0;
else if (numWays[idxN] != -1) return numWays[idxN];
else{
numWays[idxN] = 0;
if (number[idxN] != '0')
{
numWays[idxN] += count(number, numWays, n, idxN+1);
}
if (idxN+1 < n && (number[idxN]-'0')*10 + number[idxN+1]-'0' <= 26)
{
numWays[idxN] += count(number, numWays, n, idxN+2);
}
printf("numWays[%d] = %d\n", idxN, numWays[idxN]);
return numWays[idxN];
}
}
- Brett Pershing Stahlman July 24, 2014