Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A message containing letters from A-Z is being encoded to numbers using the following mapping:
'A' -> 1
'B' -> 2
...
'Z' -> 26
Given a non-empty string containing only digits, determine the total number of ways to decode it.
Example 1:
Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).
Example 2:
Input: "226"
Output: 3
Explanation: It could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).
keywords:
A - 1, ... Z- 26
ask: given digits, find total number of ways to decode it.
226 ->
first way, 2 , 2, 6 ->BBF
22, 6 VF
2, 26, BZ
total 3 ->
2 2 6
2 22 226
----------- 1 - 26
B dp[i - 1] , dp[i - 2], 22 < 26 dp[i] = dp[i - 1](i >= 1, current char is 0) + (dp[i - 2] conditional check: last two digts <= 26)
public static int FindTotalWays(string numbers) // 226
{
if(numbers == null || numbers.Length == 0) // false
{
return 0;
}
var dp = new int[length]; // 3
for(int index = 0; index < length; index++) // index = 1
{
var current = numbers[index]; // 2
var isZero = current == '0'; // '2'
// base case
if(index == 0)
{
dp[0] = isZero? 0 : 1; // 1
if(isZero)
{
return 0;
}
}
if(index > 0 && !isZero) // true
{
dp[index] += dp[index - 1]; // + dp[0] = 1
}
109
index = 2
if(index >= 1 && numbers[index - 1] != 0 && toNumber(current, numbers[index - 1]) <= 26 && toNumber(current, numbers[index - 1]) > 0 )
{
if(index == 1)
{
dp[index] += 1; // 22 -> 2 + 2
}
if(index >= 2)
{
dp[index] += dp[index - 2];
}
}
}
return dp[length - 1];
}
private static int toNumber(char current, char left)
{
var number = left - '0';
number *= 10;
number += current - '0';
return number;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.