Problem
Decode Ways
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).
Solution
226a...n has two ways of decoding.
2 26a...n
22 6a...n
the string remains also follow the 2 branch ways to decode. When the string remains is empty, we found a new way of decoding. There are 2 details, a string start with 0 can not be decoded, and a string parse to integer that bigger than 26 can not be decoded.
In order to save recalculations, the middle calculation results are memorized. We cost space O(N) to store at most N substring's decode ways, however, the time cost is reduced to O(N).
import java.util.*;
public class DecodeWays {
Map<String, Integer> memo = new HashMap<>();
public int count(String remains) {//226
if(remains == null || remains.length() == 0) {
return 1;
}
if(remains.charAt(0) == '0') return 0;
if(memo.get(remains) != null) return memo.get(remains);
int count = count(remains.substring(1));
if(remains.length() > 1 && Integer.parseInt(remains.substring(0,2)) <= 26) {
count += count(remains.substring(2));
}
memo.put(remains, count);
return count;
}
public static void main(String...args) {
DecodeWays dw = new DecodeWays();
System.out.println(dw.count("226"));
}
}
public class DecodeWays {
Map<String, Integer> memo = new HashMap<>();
public int count(String remains) {//226
if(remains == null || remains.length() == 0) {
return 1;
}
if(remains.charAt(0) == '0') return 0;
if(memo.get(remains) != null) return memo.get(remains);
int count = count(remains.substring(1));
if(remains.length() > 1 && Integer.parseInt(remains.substring(0,2)) <= 26) {
count += count(remains.substring(2));
}
memo.put(remains, count);
return count;
}
public static void main(String...args) {
DecodeWays dw = new DecodeWays();
System.out.println(dw.count("226"));
}
}
Time cost O(N), space cost O(N).
