The link to the problem: https://leetcode.com/problems/decode-ways/
A message containing letters from A-Z can be encoded into numbers using the following mapping:
'A' -> "1"
'B' -> "2"
...
'Z' -> "26"To decode an encoded message, all the digits must be mapped back into letters using the reverse of the mapping above (there may be multiple ways).
Given a non-empty string num containing only digits, return the number of ways to decode it.
The answer is guaranteed to fit in a 32-bit integer.
Example 1.
Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2, 26), "VF" (22, 6), or "BBF" (2, 2, 6).
-------------------------------------------------------------------
Example 2.
Input: s = "0"
Output: 0, since there's no character that maps to 0. Thoughts:
It’s hard to find anything at first. My first thought is that we can decode one by one. We need to find our first decoded character before finding other characters. The decoded character might be formed by a one-digit number or a two-digit number that is less than or equal to 26. After finding the first possible decoded character, we should keep doing the same thing on the rest of the string based on the previous choice until there’s no number left.
👷Let’s see if this idea works in an example input like “22678”.
🔧Step 1. Find our first decoded character. We find that we can read the first code either in 2 or 22 since they are all valid encoded numbers:
After finding our first decoded character, now we will need to find how we can decode “2678”(step 2–1) and “678”(step 2–2).
Let’s first see how we can encode “2678”.
🔧Step 2–1. Find our second decoded character. Again, we can read the next encoded number either in 2 or 26:
After finding our next decoded character, now we will need to find how we can decode “678”(step 2-1–1) and “78”(step 2–1–2).
Let’s first see how we can encode “678”.
🔧Step 2–1–1. Find our next decoded character. This time, we can only read the next encoded number in 6:
After finding our next decoded character, now we will need to find how we can decode “78”(step 2–1–1.2).
Let’s first see how we can encode “78”.
🔧Step 2–1–1.2. Find our next decoded character. This time, we can only read the next encoded number in 7:
After finding our next decoded character, now we will need to find how we can decode “8”(step 2–1–1.3).
🔧Step 2–1–1.3. Find our next decoded character. This time, we can only read the next encoded number in 8:
After finding our next decoded character, now we will need to find how we can decode “”(step 2–1–1.4).
🔧Step 2–1–1.4. Find our next decoded character. We found that we have decoded all the encoded strings. We have found all the possible decoded strings for “678”, i.e., our goal in 🔧step 2–1–1. Hence, we have found one decoded string in this path. *BBFGH (2, 2, 6, 7, 8)
💭Now, we should go finish our 🔧step 2–1–2 to decode “78”. (🔧step 2–1–2 will actually do exactly the same process in 🔧Step 2–1–1.2 ~ 2–1–1.4). We will find we can find one decoded string in here. *BZGH (2, 26, 7, 8)
💭After finish the 🔧step 2–1–2, we should go finish our 🔧step 2–2 to decode “678”. (🔧step 2–2 will do the same process in 🔧step 2–1–1~2–1–1.4). We will find we can find one decoded string here. *VFGH (22, 6, 7, 8)
🚧We have really finish all of our steps. We have found total three decoded strings from the same encoded string.
Code Logic:
If we write down the above idea, it will be like the code below. The code logic is that we use a helper method to return how many encoded ways we can find from the string that STARTS AT a certain position.
i.e., We will first call helper(“123”, 0) — which means we want to know the number of encoded ways of “123”.
We will then call helper(“123”, 1) and (“123,2) means we want to know the number of encoded ways of “23” and “3”. and etc.
After checking the current number is a valid encoded number (i.e., not zero), we can just pass the rest of the string to the helper method. Also, if the next number combines the current number can also form a new valid encoded number, we need to also pass the “new rest of the string” to the helper method.
public int numDecodings(String s) {
return helper(s, 0);
}
public int helper(String s,int indx){
if(indx==s.length()) //we're done
return 1;
int curNum = s.charAt(indx)-'0';
if(curNum==0)
return 0;
int rst = helper(s,indx+1);
if(indx+1 < s.length())
{
int nextDigit = s.charAt(indx+1)-'0';
int twoNum = curNum*10+nextDigit;
if(twoNum<=26)
rst += helper(s, indx+2);
}
return rst;
}The above code will fail on most of the test cases on Leetcode due to Time Limit Exceeded. It is not a surprising result since we might keep decoding the same strings (like “678” in the above example).
We can use a variable to record the substring that we have checked before. I decide to use a map to record a substring and its possible encoded ways. For example, “01” maps to 0, and “11” maps to 2 encoded ways.
Since we will let indx reaches the end of the string and s.substring(n) is an empty string, I will first add an empty string that maps to 1 into the map. (same logic that we will always return 1 when the index is n in the above code!)
Below is the 1ms code that beats 94% —
public int numDecodings(String s) {
Map<String,Integer> visited = new HashMap<>();
visited.put("",1);
return helper(s, 0, visited);
}
public int helper(String s,int indx,Map<String,Integer> visited){
String substr = s.substring(indx);
if(visited.get(substr)!=null)
return visited.get(substr);
int curNum = s.charAt(indx)-'0';
if(curNum==0)
{
visited.put(substr,0);
return 0;
}
int rst = helper(s,indx+1, visited);
if(indx+1 < s.length())
{
int nextDigit = s.charAt(indx+1)-'0';
int twoNum = curNum*10+nextDigit;
if(twoNum<=26)
rst += helper(s,indx+2,visited);
}
visited.put(substr, rst);
return rst;
}Or we can solve the problem iteratively by using an integer array named dp. Since this time we will start from index 0, we cannot know the ways to decode the substring that starts at i if we haven’t reached index i. Hence, this time when we reach index i, we are not going to calculate the number of encoding ways of the string that starts with i.
Instead, we are going to make use of the encoding ways of the strings before the current position. We will let dp[i] represents the number of ways of the top i characters. i.e., dp[2] represents the number of ways of the first two characters.
We will always calculate the value of dp[i] depends on the value of the ith character (i.e., index = (i-1) since it’s a zero-based array indexing) and the (i-1)th element.
In the above example when s = “22678”,
we will form the array like: [1, 1, 2, 3, 3, 3].
public int numDecodings(String s) {
int n = s.length();
int[] dp = new int[n+1];
dp[0] = 1;
for(int i=1;i<=n;i++)
{
int indx = i-1;
int curNum = s.charAt(indx) - '0';
if(curNum!=0)
dp[i] = dp[i-1];
if(i>1)
{
int prevDigit = s.charAt(indx-1) - '0';
if(prevDigit==0)
continue;
int twoNum = prevDigit*10 + curNum;
if(twoNum<=26)
dp[i] += dp[i-2];
}
}
return dp[n];
}From the above code, we can see that we actually always reference the value of dp[i-2] and dp[i-1] when we are at position i. Hence, instead of using a length of n array, we can just use two variables to record the value of those 2 values. We use prev2 to represent the value of dp[i-2], and prev to represent the value of dp[i-1].
We can get the 0ms code that beats 100% —
public int numDecodings(String s) {
int n = s.length();
if(n==1)
return s.charAt(0)=='0'?0:1;
int prev2 = 1;
int prev = s.charAt(0)=='0'?0:1;
for(int i=1;i<n;i++)
{
int curNum = s.charAt(i)-'0';
int rst = 0;
if(curNum!=0)
rst = prev;
int prevNum = s.charAt(i-1)-'0';
if(prevNum!=0)
{
int twoNum = prevNum*10 + curNum;
if(twoNum <= 26)
rst+= prev2;
}
prev2 = prev;
prev = rst;
}
return prev;
}
