一条仅包含字母‘A’-‘Z’的消息用下列的方式加密成数字
'A' -> 1 'B' -> 2 ... 'Z' -> 26现在给出加密成数字的密文,请判断有多少种解密的方法
例如:
给出的密文为“13”,可以解密为"AC"(1 3) 或者"M"(13).
所以密文"13"的解密方法是2种.
import java.util.*; public class Solution { /** * * @param s string字符串 * @return int整型 */ public int numDecodings (String s) { char[] charArray = s.toCharArray(); int length = charArray.length; if (length <= 0 ||charArray[0] == '0') { return 0; } int[] dp = new int[length]; dp[0] = 1; for (int i = 1; i < length; i++) { if (charArray[i] != '0') { dp[i] = dp[i - 1]; } int num = 10 * (charArray[i - 1] - '0') + (charArray[i] - '0'); if (num >= 10 && num <= 26){ if (i == 1) { dp[i] ++; } else { dp[i] += dp[i - 2]; } } } return dp[length - 1]; } }
public class Solution { public int numDecodings(String s) { if(s.length()==0||s.charAt(0)=='0'){ return 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-1)!='0'){ dp[i] += dp[i-1]; } if(Integer.valueOf(s.substring(i-2,i))>=10 && Integer.valueOf(s.substring(i-2,i))<=26){ dp[i] +=dp[i-2]; } } return dp[s.length()]; } }
s | 1 | 12 | 120 | 1207 | 12072 | 120723 |
dp[0] | 1 | 1 | 0 | 1 | 1 | 1 |
dp[1] | 0 | 1 | 1 | 0 | 0 | 1 |
public class Solution { public int numDecodings(String s) { if(s.length() == 0 || s.charAt(0) == '0'){ return 0; } int[][] dp = new int[2][s.length()]; dp[0][0] = 1; dp[1][0] = 0; for(int i = 1; i < s.length();i++){ if((int)s.charAt(i) == '0'){ dp[0][i] = 0; }else{ dp[0][i] = dp[0][i-1] + dp[1][i-1]; } if((s.charAt(i-1)-'1'+1)*10+(s.charAt(i)-'1'+1) <=26){ dp[1][i] = dp[0][i-1]; }else{ dp[1][i] = 0; } } return dp[0][s.length()-1]+dp[1][s.length()-1]; } }
public static int numDecodings(String s) { int n=s.length(); int[] dp=new int[n+1]; dp[n]=1; dp[n-1]=(s.charAt(n-1)=='0')?0:1; for(int i=n-2;i>=0;i--){ if(s.charAt(i)=='0')continue; if(Integer.valueOf(s.substring(i,i+2))<=26){ dp[i]=dp[i+1]+dp[i+2]; }else{ dp[i]=dp[i+1]; } } return dp[0]; } zhuyi'0'
c1=c2;c2=count;
public class Solution { public int numDecodings(String s) { if (s == null || s.length() == 0) return 0; int n = s.length(); int[] dp = new int[n + 1]; dp[0] = 1; dp[1] = s.charAt(0) == '0' ? 0 : 1; for (int i = 2; i <= s.length(); ++i) { int oneBit = Integer.parseInt(s.substring(i - 1, i)); int twoBit = Integer.parseInt(s.substring(i - 2, i)); if (oneBit >= 1 && oneBit <= 9) { dp[i] += dp[i - 1]; } if (twoBit >= 10 && twoBit <= 26) { dp[i] += dp[i - 2]; } } return dp[n]; } }
public class Solution { public int numDecodings(String s) { if(s.length()==0) return 0; int [] dp = new int[s.length()+1]; dp[0]=1; if(s.length()>0&&s.charAt(0)>'0') dp[1]=1; for(int i=2;i<=s.length();i++){ if(s.charAt(i-1)>'0') dp[i]=dp[i-1]; if(s.charAt(i-2)>'0'){ int t =Integer.parseInt(s.substring(i-2,i)); if(t<=26&&t>0) dp[i]+=dp[i-2]; } } return dp[s.length()]; } }
public class Solution { public int numDecodings(String s) { if(s.length() < 1 || s.charAt(0) == '0') return 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-1) != '0') dp[i] += dp[i-1]; if(s.charAt(i-2) == '1' || (s.charAt(i-2) == '2' && s.charAt(i-1) <= '6' && s.charAt(i-1) >= '0')) dp[i] += dp[i-2]; } return dp[s.length()]; } }
public class Solution { public int numDecodings(String s) { int n = s.length(); if (n == 0) return 0; int[] memo = new int[n+1]; memo[n] = 1; memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0; for (int i = n - 2; i >= 0; i--) if (s.charAt(i) == '0') continue; else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) ? memo[i+1]+memo[i+2] : memo[i+1]; return memo[0]; } }