# C# O(n) DP solution (Beats 90%)

• I use a DP array such that dp[i] is the number of decodings for a string of length i - 1. The reason the DP needs to be one index longer than the length is just incase the first decoding path consumes 2 letters. Either way, whether it consumes 1 letter or 2 letters, initially, the number of decodings starts at 1. If the current character I'm analyzing in the loop is not a 0 (can be consumed as 1 letter), I can simply take the number of previous decodings. If the current character can also be consumed as 2 letters, I can take the second previous decoding sum.

``````    public int NumDecodings(string s)
{
if(string.IsNullOrEmpty(s) || s[0] == '0'){
return 0;
}

int n = s.Length;
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;

for(int i = 2; i <= n; ++i){
int first = (int)Char.GetNumericValue(s[i - 1]);
int second = (int)Convert.ToInt32(s.Substring(i - 2, 2));
if(first != 0) {
dp[i] += dp[i-1];
}
if(second >= 10 && second <= 26) {
dp[i] += dp[i-2];
}
}

return dp[n];
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.