## 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