Problem:
A message containing letters from A-Z
is being encoded to numbers using the following mapping:
'A' -> 1 'B' -> 2 ... 'Z' -> 26
Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12"
, it could be decoded as "AB"
(1 2) or "L"
(12).
The number of ways decoding "12"
is 2.
Method 1: by DP
Consider the current character and the previous character.
Code for method 1:
// dp public class Solution { public int numDecodings(String s) { if (s.length() == 0) return 0; if (s.charAt(0) == '0') return 0; // at least one elements here, and not 0; int[] dp = new int[s.length()+1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= s.length(); i++){ if(s.charAt(i - 2) > '2' && s.charAt(i-1) == '0'){ dp[i] = 0; }else if (s.charAt(i - 2) > '2' && s.charAt(i-1) != '0'){ dp[i] = dp[i-1]; }else if (s.charAt(i-2) == '2' && s.charAt(i-1) >= '1' &&s.charAt(i-1) <= '6' ){ dp[i] = dp[i-1]+dp[i-2]; }else if (s.charAt(i-2) == '2' && s.charAt(i-1) == '0'){ dp[i] = dp[i-2]; }else if (s.charAt(i-2) == '2' && s.charAt(i-1) >= '7' ){ dp[i] = dp[i-1]; }else if (s.charAt(i-2) == '1' && s.charAt(i-1) != '0'){ dp[i] = dp[i-1]+dp[i-2]; }else if (s.charAt(i-2) == '1' && s.charAt(i-1) == '0'){ dp[i] = dp[i-2]; }else if (s.charAt(i-2) == '0' && s.charAt(i-1) != '0'){ dp[i] = dp[i-1]; }else{ dp[i] = 0; } } return dp[s.length()]; } }
Another more beautiful code for method 1:
public int numDecodings(String s) { if (s.length()==0||s==null||s=="0") return 0; int[] dp = new int[s.length()+1]; dp[0] = 1; if (isValid(s.substring(0,1))) dp[1] = 1; else dp[1] = 0; for(int i=2; i<=s.length();i++){ if (isValid(s.substring(i-1,i))) dp[i] += dp[i-1]; if (isValid(s.substring(i-2,i))) dp[i] += dp[i-2]; } return dp[s.length()]; } public boolean isValid(String s){ if (s.charAt(0)=='0') return false; int code = Integer.parseInt(s); return code>=1 && code<=26; }
Method 2: by Recursion. Too slow.
// by recursive public class Solution { public int numDecodings(String s) { int len = s.length(); if (len == 0) return 0; if (len == 1 ){ if (isValid(s.substring(0,1))) return 1; else return 0; } int res = 0; // at least have two elements here. if (isValid(s.substring(len-1,len))) res += numDecodings(s.substring(0,len-1)); if (isValid(s.substring(len-2, len))) res += numDecodings(s.substring(0,len-2)); return res; } public boolean isValid (String s){ if (s.length() == 0 ) return false; int i = Integer.parseInt(s); if ( i >= 1 && i <= 26 ) return true; else return false; } }