LeetCode 92 Decode Ways

简介: 版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/51339103 ...
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/51339103

原文

A message containing letters from A-Z is being encoded to numbers 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.

翻译

一条信息包括字母A-Z,它们按如下方式被映射到相应的数字:

'A' -> 1
'B' -> 2
...
'Z' -> 26

给定一个包含数字的编码信息,得出一共有多少种可能的编码方式。

例如,
给定的编码信息是“12”,它可能是“AB”(1 2),也可能是“L”(12)。

所以“12”的编码方式有2种。

代码

题目看了半天才看懂,沮丧脸……

由于是在LeetCode上尝试分类结题,这题被归在了String下面,我以为只是简单的字符串操作就可以搞定,后来发现遍历过程是动态的,也就是要用到DP了。

由于现在对DP还不是很熟练,所以没能解出来,先借用大神的代码来占个坑吧。

bool valid(string s) {
    if (s[0] == '0')
        return false;
    if (s[0] > '2' || (s[0] == '2' && s[1] > '6'))
        return false;
    return true;
}

int numDecodings(string s) {
    int len = s.length();
    if (len == 0 || s[0] == '0') return 0;
    vector<int> dp(len + 1, 0);
    dp[0] = 1;
    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (s[i - 1] != '0') 
            dp[i] += dp[i - 1];
        if (valid(s.substr(i - 2, 2))) 
            dp[i] += dp[i - 2];
        if (dp[i] == 0) 
            return 0;
    }
    return dp[len];
}
目录
相关文章
|
存储
LeetCode 394. Decode String
给定一个经过编码的字符串,返回它解码后的字符串。 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。 你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。 此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
73 0
LeetCode 394. Decode String
LeetCode 91. Decode Ways
字母A到Z分别和1到26的数字一一对应,给定一串用字符表示的数字,将数字串从不同位置拆开,每一个数字都对应一个字符,如此构成了一个字母字符串. 从不同的位置拆分数字字符串,可以得到不同的字母字符串,问一共有多少种有效的拆分方式.
54 0
LeetCode 91. Decode Ways
|
Java Python
LeetCode 394:字符串解码 Decode String
题目: 给定一个经过编码的字符串,返回它解码后的字符串。Given an encoded string, return its decoded string. 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。
1015 0
LeetCode 91 Decode Ways(编码方式)(*)
版权声明:转载请联系本人,感谢配合!本站地址:http://blog.csdn.net/nomasp https://blog.csdn.net/NoMasp/article/details/51340198 ...
957 0
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
索引
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值
【LeetCode刷题】二分查找:山脉数组的峰顶索引、寻找峰值