【把数字翻译成字符串】leetcode： 91. 解码方法
给定一个数字，按照如下规则翻译成字符串：0翻译成“a”，1翻译成“b”…25翻译成“z”。一个数字有多种翻译可能，例如12258一共有5种，分别是bccfi，bwfi，bczi，mcfi，mzi。实现一个函数，用来计算一个数字有多少种不同的翻译方法。
自上而下，从最大的问题开始，递归 ：
12258
/\
b+2258m+258
/\/\
bc+258bw+58mc+58mz+8
/\\\\
bcc+58 bcz+8bwf+8mcf+8mzi
/\\\
bccf+8bczibwfimcfi
/
bccfi
有很多子问题被多次计算，比如258被翻译成几种这个子问题就被计算了两次。
用dp来解决，当选中为第i位时，它有两种选择，一、自身1个数，此时dp[i] = dp[i-1]；二、和第i-1位构成一个数字，dp += dp[i-1]。也就是说dp[i]起码等于dp[i-1]，因为它自身是一个数字；要考虑能不能和i-1构成一个两位数，这个两位数是有限制的，首先要小于25，如果十位是1，个位是几都可以，如果十位是2，个位只能小于6。（leetcode是1~26所以还要判断是否有0,0的话就只能为0）
class Solution {
public:
int numDecodings(string s) {
if(s.empty())return 0;
vector dp(s.size()+1,0);
dp[0] = 1;
for(int i = 1;
i1 && (s[i-2] == '1' || (s[i-2] == '2' && s[i-1] <'6')))
dp[i] +=dp[i-2];
}
return dp.back();
}
};
推荐阅读
- 牛牛以前在老师那里得到了一个正整数数对(x, y), 牛牛忘记他们具体是多少了。 但是牛牛记得老师告诉过他x和y均不大于n, 并且x除以y的余数大于等于k。 牛
- 剑指offer|剑指offer、牛客-二维数组的查找
- 剑指offer|牛客网_剑指Offer_Python实现_更新中
- 剑指offer|牛客网剑指offer——python实现（更新15题）
- 剑指Offer__17、树的子结构
- 剑指Offer__19、顺时针打印矩阵
- 剑指Offer__18、二叉树的镜像
- 输入一个英文句子，将每个单词的第一个字母改成大写字母。
- Leetcode|【leetcode】 91. 解码方法 & 【剑指Offer】 46.把数字翻译成字符串
- 【剑指offer】包含min函数的栈