@@ -0,0 +1,1974 @@
+// A message containing letters from A-Z is being encoded to numbers using the following mapping:%0A%0A// 'A' -%3E 1%0A// 'B' -%3E 2%0A// ...%0A// 'Z' -%3E 26%0A// Given an encoded message containing digits, determine the total number of ways to decode it.%0A%0A// For example,%0A// Given encoded message %2212%22, it could be decoded as %22AB%22 (1 2) or %22L%22 (12).%0A%0A// The number of ways decoding %2212%22 is 2.%0A%0Apublic class Solution %7B%0A%09// use recursive dfs and DP to solve this problem respectively.%0A%09// Firstly gives out the dfs approach :: TLE%0A    // public int numDecodings(String s) %7B%0A    // %09int sLen = s.length();%0A%0A    //     if(sLen == 0)%7B%0A    //     %09return sLen;%0A    //     %7D%0A%0A    //     int%5B%5D counter = %7B0%7D;%0A%0A    //     dfs(s, sLen, 0, counter);%0A%0A    //     return counter%5B0%5D;%0A    // %7D%0A%0A    // public void dfs(String s, int sLen, int index, int%5B%5D counter)%7B%0A    // %09if(index == sLen)%7B%0A    // %09%09counter%5B0%5D += 1;%0A    // %09%09return;%0A    // %09%7D%0A%0A    // %09for(int i = index; i %3C sLen; i++)%7B%0A    // %09%09String tempString = s.substring(index, i);%0A    // %09%09if(isValid(tempString))%7B%0A    // %09%09%09dfs(s, sLen, i, counter);%0A    // %09%09%7D%0A    // %09%7D%0A    // %7D%0A%0A    public boolean isValid(String s, int start, int end)%7B%0A    %09if(end - start == 0 %7C%7C end %3E s.length()) return false;%0A%0A    %09String subS = s.substring(start, end);%0A    %09int num = Integer.parseInt(subS);%0A    %09int subLen = subS.length();%0A%0A    %09if(subLen == 1)%7B%0A    %09%09return num %3E 0 && num %3C= 9;%0A    %09%7Delse%7B%0A    %09%09return num %3E 9 && num %3C= 26;%0A    %09%7D%0A    %7D%0A%0A    public int numDecodings(String s) %7B%0A    %09int sLen = s.length();%0A    %09%0A    %09if(sLen == 0 %7C%7C s.charAt(0) == '0') return 0;%0A%0A    %09int%5B%5D dp = new int%5BsLen + 1%5D;%0A    %09dp%5B0%5D = isValid(s, 0, 1)? 1 : 0;%0A    %09dp%5B1%5D = isValid(s, 1, 2)? dp%5B0%5D : 0;%0A    %09dp%5B1%5D = isValid(s, 0, 2)? dp%5B1%5D + dp%5B0%5D : dp%5B1%5D;%0A%0A    %09for(int i = 2; i %3C sLen; i++)%7B%0A    %09%09if(isValid(s, i, i + 1))%7B%0A    %09%09%09dp%5Bi%5D = dp%5Bi - 1%5D;%0A    %09%09%7D%0A    %09%09if(isValid(s, i - 1, i + 1))%7B%0A    %09%09%09dp%5Bi%5D += dp%5Bi - 2%5D;%0A    %09%09%7D%0A    %09%7D%0A%0A    %09return dp%5BsLen - 1%5D;%0A    %7D%0A%7D

add decode ways solution