LeetCode 91 解码方法
91. 解码方法
Difficulty: 中等
一条包含字母 A-Z
的消息通过以下方式进行了编码:
'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串,请计算解码方法的总数。
示例 1:
输入: "12"
输出: 2
解释: 它可以解码为 "AB"(1 2)或者 "L"(12)。
示例 2:
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
Solution
Language: C++
暴力求解之路
刚开始这道题, 没有太好思路, 但是首先对于算法菜鸟来讲,这类多少种情况的题肯定能用笨方法暴力回溯来解决. 写回溯的呢,就是要明白 ①回溯的截止条件 ② 回溯的当前深度,有哪些选择 ③ 做出选择, 更新参数 递归回溯方法 ④ 恢复之前的选择影响(也就是前一步的副作用) ,做下一种选择.
这里应该不需要将可能的解法保存起来, 只是求数量, 不需要破坏原字符串,也就不需要恢复操作.
解码方法,这里是 数字 转换成 字符. 所以这题的难点是有不少边缘case处理.
首先字符是从 'A' -> 'Z'
对应的数字是从 1 -> 26
, 也就是说我们去解码字符串的时候, 可以选一个, 也可以选2个数字.
如果选择一个, 那么这个字符不能为 '0' ;
如果选择两个, 那么 前后两个字符不能超过 26
, 也就是只能是 '1X' -> '2Y'
, X
可以是 0-9
, Y
只能是 0-6
.
所以整体需要去做很多 if-else
判断.
class Solution
{
public:
int total;
int numDecodings(string s)
{
if (s.empty() || s[0] == '0')
return 0;
// 暴力的方式, 回溯算法 截取一个或者两个
total = 0;
numDecodings(s, 0, s.length());
return total;
}
void numDecodings(string &s, int cur, int end)
{
if (cur == end)
{
total++;
return;
}
// 选择
if (s[cur] == '0')
{
return;
}
else if (s[cur] == '1')
{
if (cur <= (end - 2))
{ // 可以选两个
numDecodings(s, cur + 1, end);
numDecodings(s, cur + 2, end);
}
else
{
numDecodings(s, cur + 1, end);
}
}
else if (s[cur] == '2')
{
if (cur <= (end - 2) && s[cur + 1] <= '6')
{ // 可以选两个
numDecodings(s, cur + 1, end);
numDecodings(s, cur + 2, end);
}
else
{
numDecodings(s, cur + 1, end);
}
}
else
{
numDecodings(s, cur + 1, end);
}
}
};
上面的暴力解法时间复杂度会很高. O(n^2) 所以提交后 ,会出现超时的.
223 / 258 个通过测试用例
,卡住的测试用例
"9371597631128776948387197132267188677349946742344217846154932859125134924241649584251978418763151253"
另外分支判断比较杂乱, 其实按照最开始的分析,取两位解码的话可以合并处理
class Solution
{
public:
int total;
int numDecodings(string s)
{
if (s.empty() || s[0] == '0')
return 0;
total = 0;
numDecodings(s, 0, s.length());
return total;
}
void numDecodings(string &s, int cur, int end)
{
// 能走到最后,可能说明解码成功了
if (cur == end)
{
total++;
return;
}
// 无效解码
if (s[cur] == '0') return;
//如果可以选两个进行解码
if (cur <= (end - 2)) {
if (s[cur] == '1' ||
(s[cur] == '2' && s[cur + 1] <= '6')) {
numDecodings(s, cur + 2, end);
}
}
// 绝对可以解码1个的
numDecodings(s, cur + 1, end);
}
};
优化后的结果, 可以发现少做了很多判断后提交AC了 , 当然耗时同样很大.
258 / 258 个通过测试用例
状态:通过
执行用时:1016 ms
内存消耗:8.7 MB
合理的递归 与 记忆优化
既然是递归, 那么很容易就会想到优化的方式就是采用 记忆化递归 , 解决递归树中的重复子问题.
例如合法的连续两次解码1位数值 和 一次合法的 解码2位数值, 后面的解码是重复的, 那么我们完全可以采用空间换时间的方式, 存储从该索引到尾部索引这个字符串的解码结果是否成功的标志. 不过尴尬😓的是,我上面的写法完全做不到记录解码结果的样子.
上面的写法是不推荐的,因为这个思路是类似人肉递归的方式, 一直追溯到底部是否解码成功.
推荐的做法是,仅关心当前的解码是否可行, 然后观察后面的解码和当前的解码有什么关系. 让计算机自己递归去解决就可以了.
切忌, 千万不要人肉递归 普通人的脑力完全递归不了几层就出岔子了, 聪明人也不会去那么做 😭 .
同时关于取两位的分支判断: 我们这次从数字的角度看, 只需要查看相邻两位转数字(stoi()
)后是不是 10 <= number <= 26
即可. 两个字符合并起来的可读性,没这个好理解. 根据上面分析有了下面代码
class Solution
{
public:
int numDecodings(string s)
{
if (s.empty() || s[0] == '0')
return 0;
if (s.length() == 1)
return 1;
return numDecodings(s, 0, s.length() - 1);
}
int numDecodings(string &s, int begin, int end)
{
// 无效解码
if (s[begin] == '0')
return 0;
// 仅一位数字 (排除了'0'),有效解码
if (end - begin <= 0)
return 1;
// 起码两位长度的字符串了
// 先取一位
int count = numDecodings(s, begin + 1, end);
const int value = stoi(s.substr(begin, 2));
// 再取两位
if (value <= 26)
count += numDecodings(s, begin + 2, end);
return count;
}
};
239 / 258 个通过测试用例 卡在了
"1787897759966261825913315262377298132516969578441236833255596967132573482281598412163216914566534565"
哈哈 可怜的stoi , 导致超时了
下面是 换成 s[begin] == '1' || (s[begin] == '2' && s[begin+1] <= '6')
字符判断, AC 了 啪啪打脸 😭
class Solution
{
public:
int numDecodings(string s)
{
if (s.empty() || s[0] == '0')
return 0;
if (s.length() == 1)
return 1;
return numDecodings(s, 0, s.length() - 1);
}
int numDecodings(string &s, int begin, int end)
{
// 无效解码
if (s[begin] == '0')
return 0;
// 仅一位数字 (排除了'0'),有效解码
if (end - begin <= 0)
return 1;
// 起码两位长度的字符串了
// 先取一位
int count = numDecodings(s, begin + 1, end);
// stoi时间复杂度太高, 导致提交失败ಥ_ಥ
// 再取两位
if (s[begin] == '1'
|| (s[begin] == '2' && s[begin+1] <= '6'))
count += numDecodings(s, begin + 2, end);
return count;
}
};
258 / 258 个通过测试用例
状态:通过
执行用时:1160 ms
内存消耗:8.8 MB
递归加上记忆优化吧
class Solution
{
public:
// 比使用数组效果更好
unordered_map<int,int> memo;
int numDecodings(string s)
{
if (s.empty())
return 0;
return numDecodings(s, 0, s.length() - 1);
}
private:
int numDecodings(const string &s, int begin, int end)
{
if (memo.count(begin))
return memo[begin];
// 无效解码
if (s[begin] == '0')
return 0;
// 仅一位数字 (排除了'0'),有效解码
if (begin>=end)
return 1;
// 起码两位长度的字符串了
// 先取一位
int count = numDecodings(s, begin + 1, end);
// 再取两位 查看花花酱大神的代码实现,发现简单实现 stoi 效率比直接判断字符还高 ಥ_ಥ
const int prefix = (s[begin] - '0') * 10 + (s[begin + 1] - '0');
if (prefix <= 26)
count += numDecodings(s, begin + 2, end);
// 记忆
memo[begin] = count;
return count;
}
};
执行用时 :4 ms, 在所有 C++ 提交中击败了73.17%的用户
内存消耗 :9.9 MB, 在所有 C++ 提交中击败了5.06%的用户
此处的优化是, 使用 (s[begin] - '0') * 10 + (s[begin + 1] - '0')
计算 stoi 比 判断 s[begin] == '1' || (s[begin] == '2' && s[begin+1] <= '6')
快了4ms, 反转又被啪啪打脸 😭
而使用 vector
记录和使用 unordered_map
效率差不多.
动态规划
从上面的代码分析可以看出,这种递归树,往往可以采用自底向上的动态规划处理, 或者经常刷题的小伙伴
可能感觉上面的递归树如果由底向上的话, 这个很类似斐波那契或者爬楼梯的意思.
做动态规划的步骤
- 找状态定义, 不同的状态定义可能导致不同的时间复杂度;
- 状态定义要包含 变化的条件
- 这里定义为: dp[i] 为 索引 0~i的子字符串的解码数量
- 找状态迁移方程
- 当前索引 i 的字符串 可以从 i-1的位置解码过来, 或者 i-2的解码位置过来
- 也就是 dp[i] = dp[i-1] + dp[i-2] 的值
下面题解
class Solution {
public:
int numDecodings(string s)
{
if (s.empty() || s[0] == '0')
return 0;
if (s.length() == 1) return 1;
// 定义 dp[i] 为从0~i的子字符串的解码情况
vector<int> dp(s.length(),0);
// 空字符串 解码为一种
// dp[-1] = 1; 不支持 索引为-1,所以后面要注意dp[i-2]的判断
// 单个字符的话(排除了'0') 解码为一种
dp[0] = 1;
/// 我们仅仅需要累计 解码一个字符与解码两个字符 的情况即可
for (int i = 1; i< s.length();++i) {
if (!isValid(s[i]) && !isValid(s[i-1],s[i])) { // 如果s[i] 无效 且 s[i]s[i-1] 那么不管s[i-2]如何大,都没用,后面的两个数值都无法完成解码
// dp[i] = 0 + 0; // 这里直接就可返回了,很明显当前无解,后面也无解
return 0;
} else if (!isValid(s[i]) && isValid(s[i-1],s[i])) { // 如果 s[i] 无效, s[i-1][i] 有效, 说明两个字符的解码成功, 一个字符的解码失败
dp[i] = 0 + (i == 1 ? 1 : dp[i-2]);
} else if (isValid(s[i]) && !isValid(s[i-1],s[i])) { // 如果 s[i] 有效 s[i-1]s[i] 无效 ,那么 说明两个字符的没有解码成功, 一个字符的解码成功了
dp[i] = dp[i-1] + 0;
} else { // 肯定是 两个都有效了
dp[i] = dp[i-1] + (i == 1 ? 1 : dp[i-2]);
}
}
return dp[s.length() - 1];
};
private:
bool isValid(const char c) { return c != '0'; }
bool isValid(const char c1, const char c2) {
const int num = (c1 - '0')*10 + (c2 - '0');
return num >= 10 && num <= 26;
}
};
执行用时 :0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗 :8.6 MB, 在所有 C++ 提交中击败了11.05%的用户
时间复杂度 O(n)
空间复杂度 O(n)
由于状态迁移方程 dp[i] = dp[i-1] + dp[i-2]
可以知道, 当前状态仅仅和前两个状态有关, 所以空间优化可以采用 两个变量, 迭代更新即可.类似 斐波那契方程
class Solution {
public:
int numDecodings(string s)
{
if (s.empty() || s[0] == '0')
return 0;
if (s.length() == 1) return 1;
// 空字符串 解码为一种
int pre0 = 1; // dp[-1]
int pre1 = 1; // dp[0]
for (int i = 1; i< s.length();++i) {
int temp = 0; // 当前的解码值
if (!isValid(s[i]) && !isValid(s[i-1],s[i])) {
return 0;
} else if (!isValid(s[i]) && isValid(s[i-1],s[i])) {
temp = pre0;
} else if (isValid(s[i]) && !isValid(s[i-1],s[i])) {
temp = pre1;
} else {
temp = pre0 + pre1;
}
// 更新
pre0 = pre1;
// 最后的值
pre1 = temp;
}
return pre1;
};
private:
bool isValid(const char c) { return c != '0'; }
bool isValid(const char c1, const char c2) {
const int num = (c1 - '0')*10 + (c2 - '0');
return num >= 10 && num <= 26;
}
};
执行用时 :4 ms, 在所有 C++ 提交中击败了73.17%的用户
内存消耗 :8.5 MB, 在所有 C++ 提交中击败了31.79%的用户
时间复杂度 O(n)
空间复杂度 O(1)
比较记忆化递归的效率会发现比优化后的动态规划还要高效. 哈哈
Discussion