一条仅包含字母‘A’-‘Z’的消息用下列的方式加密成数字
'A' -> 1 'B' -> 2 ... 'Z' -> 26现在给出加密成数字的密文,请判断有多少种解密的方法
例如:
给出的密文为“13”,可以解密为"AC"(1 3) 或者"M"(13).
所以密文"13"的解密方法是2种.
/* 动态规划。 主要是要对0讨论。 */ public int numDecodings(String s) { int len = s.length(); if (len == 0) return 0; if (s.charAt(0) == '0') return 0; int[] dp = new int[len + 1]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= len; i++) { if (s.charAt(i - 1) == '0' && s.charAt(i - 2) != '1' && s.charAt(i - 2) != '2') return 0; if ((s.charAt(i - 2) == '1' && s.charAt(i - 1) >= '1' && s.charAt(i - 1) <= '9' )|| (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) == '1' || s.charAt(i - 2) == '2') && s.charAt(i - 1) == '0') { dp[i] = dp[i - 2]; } else { dp[i] = dp[i - 1]; } } return dp[len]; }
class Solution { public: int numDecodings(string s) { /** dp[i] 表示i的字符的合法编码数量,取决于当前字符 dp[i] += dp[i-1],if s[i-1] ~('0'--'9') dp[i] += dp[i-2],if s[i-2] == '1' || (s[i-2]=='2' && s[i-1]>='0' && s[i-1]<='6') **/ if(s.length()==0 || s[0] == '0') return 0; int len = s.length(); vector<int> dp(len+1,0); dp[0]= 1,dp[1] = 1; for(int i=2;i<=len;i++) { if(s[i-1]>='1' && s[i-1]<='9') dp[i] += dp[i-1]; if(s[i-2]=='1' || (s[i-2]=='2' && s[i-1]>='0' && s[i-1]<='6')) dp[i] += dp[i-2]; } return dp[len]; } };
public class Solution { public int numDecodings(String s) { if(s == null || s.length() == 0 || s.charAt(0) == '0') return 0; for(int i = 0; i < s.length(); i++){ if(!Character.isDigit(s.charAt(i))) return 0; } // dp[i]表示s[0~i-1]可以有多少种解码方式 // 递推方程:如果1 <= s[i-1] <= 9,则dp[i] += dp[i-1]; // 如果10 <= s[i-2 ~ i-1] <= 26, 则dp[i] += dp[i-2]. 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) >= '1' && s.charAt(i-1) <= '9') 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()]; } }
/* * 思路:dp题。 * 状态定义:dp[i]表示s[0 ~ i-1]子串能解码的种类 * 递推方程:如果1 <= s[i-1] <= 9,则dp[i] += dp[i-1]; 如果10 <= s[i-2 ~ i-1] <= 26, 则dp[i] += dp[i - 2]. * 初始状态:dp[0] = 1, dp[1] = 1; * 注意:当s以0开头时,返回0 */ public class Solution { public int numDecodings(String s) { if (s.length() == 0 || s.startsWith("0")) return 0; int len = s.length() + 1; int[] dp = new int[len]; dp[1] = 1; dp[0] = 1; for (int i = 2; i < len; i++) { int t = Integer.valueOf(s.substring(i - 2, i)); if (10 <= t && t <= 26) { dp[i] += dp[i - 2]; } //注意0在这里要特殊对待 int tmp = Integer.valueOf(s.substring(i - 1, i)); if (1 <= tmp && tmp <= 9) { dp[i] += dp[i - 1]; } } return dp[len - 1]; } }
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()]; } }
import java.util.*; public class Solution { public int numDecodings(String s) { if (s.length() == 0 || s.charAt(0) == '0') return 0; if (s.length() == 1) return 1; int f[] = new int[s.length() + 1]; f[0] = 1; // 当有0个字符时候的编码个数,当有连续两个字符能编码时f[i] = f[i-2],保证f[0]有值 f[1] = 1; // 字符串长度为1时的编码个数 for (int i = 1; i < s.length(); i++) { String num = s.substring(i - 1, i + 1); // 两个字符能否拼成一个编码 if (Integer.valueOf(num) <= 26 && s.charAt(i - 1) != '0') { f[i + 1] = f[i + 1 - 2]; } // 单个字符能够构成编码,如果含0,则不能编码。 f[i + 1] += s.charAt(i) != '0' ? f[i + 1 - 1] : 0; } return f[s.length()]; } }
/*解题思路, 设dp[i+1]为s.sub(0,i)的解码个数 1.当s的第i个字符为0时,要想s.sub(0,i-1)加入这个‘0’后还能解码,就只能将s.sub(0,i-1)的最后一个字符尝试与'0'拼接,并且凭借后的字符还要小于26,否则,加上s.sub(0,i-1)加上'0' 后一定会导致s.sub(0,i)没有解码方式。所以综上所述只有s.at(i-1)=='1'或是s.at(i-1)=='2'才可以使拼接后小于26,并且此时s.sub(0,i)的解码个数和s.sub(0,i-2)一致。 2.当s的第i个字符为1~9时: (1)如果s.at(i-1)是'1',那么,第i个字符可以单独解码,也可以与第i-1个字符合并组成一个码字,这种情况下s.sub(0,i)的解码个数为s.sub(0,i-1)的解码个数与s.sub(0,i-2)的解码个数之和。 (2)如果s.at(i-1)是'2'且'6'>=s.at(i)>='1',那么此时第i个符号也可以与i-1个合并,这种情况下s.sub(0,i)的解码个数同样为s.sub(0,i-1)的解码个数与s.sub(0,i-2)的解码个数之和。 (3)其他情况下,也就是'7'<=s.at(i)<='9'&&s.at(i-1)=='2'和'1'<=s.at(i)<='9'&&3<=s.at(i-1)<=9这两种情况下,第i个字符不能与i-1个字符合并,只能自己单独作为一个码字,所以此时.sub(0,i)的解码个数和s.sub(0,i-1)一致。 */ class Solution { public: int numDecodings(string s) { if(s==""||s.at(0)=='0') return 0; int len_of_s=s.length(); vector<int> dp(len_of_s+1); dp[0]=1;//空字符也是一种解码 dp[1]=1;//如果s的第一个字符不是0,那么直到s的第一个字符含有1中解码 for(int i=1;i<len_of_s;i++) { if(s.at(i)=='0') { if(s.at(i-1)=='1'||s.at(i-1)=='2') dp[i+1]=dp[i-1]; else return 0; } else { if(s.at(i-1)=='1'||(s.at(i)<='6'&&s.at(i-1)=='2')) dp[i+1]=dp[i-1]+dp[i]; else dp[i+1]=dp[i]; } } return dp[len_of_s]; } }; /*方法2 class Solution { //***递归超时了 public: int numDecodings(string s) { int long_of_s=s.length(); int decode_ways=0; int start; decode(decode_ways,0,long_of_s,s); return decode_ways; } void decode(int &decode_ways,int start,int long_of_s,string s) { for(int i=0;i<2;i++) { //i==0就是只包含start,i==1就是包含两位,最多只可能包含两位三位一定大于26 if(start==long_of_s-1&&i==1) return; //当到了s的最后一位,i就只能等于0,等于1就是错误的,所以在这个特例下需要return if((i==1&&stoi(s.substr(start,i+1))>9&&stoi(s.substr(start,i+1))<27)||(i==0&&stoi(s.substr(start,i+1))>0&&stoi(s.substr(start,i+1))<10)) { //当从start开始截取i+1个符号对应的的数字小于26,之所以不采用stoi(s.substr(start,i+1))>0&&stoi(s.substr(start,i+1))<27)这种写法的原因是,防止在截取两位数时出现01、02...0x这种误判,这种情况是没有解码方式的,可以采样那种写法却会判定他们为一种解码方式 if(start+i==long_of_s-1) { //当发现这次截取已经包含s的最后一个字符,就停止向更深处递归,并方式加一 decode_ways++; return; } decode(decode_ways,start+i+1,long_of_s,s); //没到最深处继续递归,如果i==0,那其实就是start下一位,i==1,就是下下一位 } }//其他的可能性就是从当从start开始截取i+1个还没到最后一位且对应的数字不在1~26范围内,此时我们不向更深处递归,等到i==2的时候如果还不满足截取数字在1~26的话,本次调用就自动结束了,不用做多于处理! } };*/
public class Solution { public int numDecodings(String s) { int size = s.length(); if(size == 0) return 0; int[] dp = new int[size + 2]; dp[0] = 1; dp[1] = 1; for(int i = 2; i <= size + 1; i++){ dp[i] = dp[i - 2] * isOk(s, i - 3, i - 1) + dp[i - 1] * isOk(s, i - 2, i - 1); } return dp[size + 1]; } public int isOk(String s, int begin, int end){ if(begin < 0) return 0; String subStr = s.substring(begin, end); int value = Integer.parseInt(subStr); return value <= 26 && value >= 1 && Integer.toString(value).length() == subStr.length() ? 1 : 0; } }
class Solution { public: int numDecodings(string s) { int len = s.length(); if(len==0||s[0]=='0') return 0; int dp[100000]; dp[0]=1; dp[1]=1; for(int i=2;i<=len;i++){ if((s[i-2]=='2'&&s[i-1]<='6') || (s[i-2]=='1'&&s[i-1]<='9')){ //状态转移方程 dp[i]=dp[i-1]+dp[i-2]; if(s[i-1]=='0') dp[i]=dp[i-2]; }else if(s[i-1]=='0'){ return 0; }else{ dp[i]=dp[i-1]; } } return dp[len]; } };
public class Solution { public int numDecodings(String s) { if(s==null||s.length()==0) return 0; int[]dp=new int[s.length()+1]; dp[0]=1; if(s.charAt(0)=='0') { return 0; } dp[1]=1; for(int i=2;i<s.length()+1;i++) { if((s.charAt(i-1)<='9')&&(s.charAt(i-1)>='1')) dp[i]=dp[i]+dp[i-1]; if(((s.charAt(i-1)>='0')&&(s.charAt(i-1)<='6')&&(s.charAt(i-2)=='2'))||s.charAt(i-2)=='1') dp[i]=dp[i]+dp[i-2]; } return dp[s.length()]; } }
class Solution { public: bool isValid(string s) { stringstream ss(s); int num; ss >> num; if(s.size()>1) return s[0]!='0' && num>=1 && num<=26; return num>=1 && num<=26; } int numDecodings(string s) { int len=s.size(); if(len ==0 ) return 0; vector<int> dp(len+1); dp[0] = 1; string s1; for(int i=1;i<=len;i++) { for(int j=0;j<i;j++) { s1 = s.substr(j,i-j); if(isValid(s1)) { dp[i] += dp[j]; } } } return dp[len]; } };
这道题思考了两天半才完全弄明白。。。 class Solution { public: int numDecodings(string s) { int len=s.size(); if(len<=0) return 0; vector<int> dp(len+1); dp[0]=1; if(s[0]!='0') dp[1]=1; else dp[1]=0; for(int i=2;i<=len;++i) { if(s[i-1]!='0') dp[i]=dp[i-1]; else dp[i]=0; if(s[i-2]=='1'||(s[i-2]=='2'&&s[i-1]<='6')) dp[i]=dp[i]+dp[i-2]; } return dp[len]; } };
class Solution { public: int numDecodings(string s) { int l = s.length(); if(l==0 || s[0]=='0') return 0; vector<int> dp(l+1,0); dp[0] = 1; dp[1] = 1; for(int i=2;i<=l;i++) { if(s[i-1]>='1' && s[i-1]<='9') dp[i] += dp[i-1]; if(s[i-2]=='1' || (s[i-2]=='2' && s[i-1]>='0' && s[i-1]<='6')) dp[i] += dp[i-2]; } return dp[l]; } };
class Solution { public: int numDecodings(string s) { if(s.empty())return 0; vector<int> dp(s.size(),0); dp[0]=s[0]-'0'>0?1:0; for(int i=1;i<s.size();++i){ int tmp=stoi(s.substr(i-1,2)); dp[i]=(s[i]-'0'>0?dp[i-1]:0)+(tmp<=26 && tmp>=10?(i==1?1:dp[i-2]):0); } return dp[s.size()-1]; } };
public int numDecodings(String s) { if (s == null || s.length() == 0) { return 0; } int len = s.length(); int[] res = new int[len + 1]; res[len] = 1; res[len-1] = s.charAt(len - 1) == '0' ? 0 : 1; for (int i = len - 2; i >= 0; i--) { if (s.charAt(i) == '0') continue; else { res[i] = Integer.parseInt(s.substring(i, i + 2)) <= 26 ? res[i + 1] + res[i + 2] : res[i + 1]; } } return res[0]; }
public int numDecodings(String s) { int len=s.length(); if(len==0){ return 0; } if(s.charAt(0)=='0'){ return 0; } int[] dp=new int[len]; if(len==1){ return 1; } dp[0]=1; if(s.charAt(1)=='0'&&s.charAt(0)>'2'){ return 0; }else if((s.charAt(0)=='1'&&s.charAt(1)>'0')||(s.charAt(0)=='2'&&s.charAt(1)>'0'&&s.charAt(1)<='6')){ dp[1]=2; }else{ dp[1]=1; } if(len==2){ return dp[1]; } for(int i=2;i<len;i++){ if(s.charAt(i)=='0'&&(s.charAt(i-1)>'2'||s.charAt(i-1)=='0')){ return 0; }else if((s.charAt(i-1)=='1'&&s.charAt(i)>'0')||(s.charAt(i-1)=='2'&&s.charAt(i)>'0'&&s.charAt(i)<='6')){ dp[i]=dp[i-1]+dp[i-2]; }else if((s.charAt(i-1)=='1'&&s.charAt(i)=='0')||(s.charAt(i-1)=='2'&&s.charAt(i)=='0')){ dp[i]=dp[i-2]; }else{ dp[i]=dp[i-1]; } } return dp[len-1]; }
}
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]; } }
这个动态规划有点难,因为f(i)不仅与f(i-1)有关,和f(i-2)也有关系,能想明白这一层关系着实不容易0.0
设当前的解法有f(i)种,由于s[i]和s[i - 1]的搭配方式有多种,下面分情况讨论:
f(i)=f(i-1)
,如果能搭配成两种,那么f(i)=f(i-1)+f(i-2)
class Solution { public: /** * * @param s string字符串 * @return int整型 */ int numDecodings(string s) { // write code here if(s.size() < 1 || s[0] == '0') return 0; int a = 1, b = 1, dp = 1; for (int i = 1; i < s.size(); ++i) { // 非法的情况 if (s[i] == '0' && (s[i - 1] > '2' || s[i - 1] == '0')) return 0; // 合法的情况之可拆 if (s[i] != '0' && ((s[i - 1] == '1') || (s[i - 1] == '2' && s[i] < '7'))) dp = a + b; // 合法的情况之不可拆 else dp = b; a = b; b = dp; } return dp; } };
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 int numDecodings (String s) { // write code here char cs[] = s.toCharArray(); int n = cs.length; int[] dp = new int[n]; if (n==0) return 0; if ("0".equals(s)) return 0; if (n==1) return 1; if (cs[1]!='0'&&((cs[0]=='1')||(cs[0]=='2'&&cs[1]<='6'))){ dp[0] = 1; dp[1] = 2; }else { dp[0] = 1; dp[1] = 1; } for (int i = 2; i < n; i++) { if (cs[i]=='0'&&(cs[i-1]=='1'||cs[i-1]=='2')) dp[i] = dp[i-2]; else if (cs[i]==0) return 0; else if (cs[i-1]=='0') dp[i] = dp[i-1]; else if (cs[i-1]=='1') dp[i] = dp[i-1] + dp[i-2]; else if (cs[i-1]=='2'&&cs[i]<='6') dp[i] = dp[i-1] + dp[i-2]; else dp[i] = dp[i-1]; } return dp[n-1]; }