- 递归解法
class Solution
{
public:
int numDecodings(string s)
{
return getAns(s, 0);
}
private:
int getAns(string s, int start)
{
if (start == s.length())
{
return 1;
}
if (s[start] == '0')
{
return 0;
}
int ans1 = getAns(s, start + 1); //得到第一种划分的解码方式
int ans2 = 0;
if (start < s.length() - 1)
{
int ten = (int)(s[start] - '0') * 10;
int one = (int)(s[start + 1] - '0') * 1;
if (ten + one <= 26)
{
ans2 = getAns(s, start + 2);
}
}
return ans1 + ans2;
}
};
这种解法超时。
- 带记忆的递归解法
class Solution
{
public:
int numDecodings(string s)
{
return getAns(s);
}
private:
int getAns(string s)
{
if (s.length() == 0)
{
return 1;
}
if (datamap.count(s))
{
return datamap[s]; //s已经计算过 并存在了map中
}
if (s[0] == '0')
{
return 0;
}
if (1 == s.length())
{
return 1;
}
int ans1 = getAns(s.substr(1)); //得到第一种划分的解码方式
const int prefix = stoi(s.substr(0, 2));
int ans2 = 0;
if (prefix <= 26)
{
ans2 = getAns(s.substr(2));
}
datamap[s] = ans1 + ans2;
return ans1 + ans2;
}
private:
unordered_map<string, int> datamap; //存储已经计算过的字符串
};
- 由暴力递归而来的DP解法
class Solution
{
public:
int numDecodings(string s)
{
int length = s.length();
vector<int> dp(length + 1);
int profix = 0;
dp[length] = 1;
if(s[length - 1] != '0')
{
dp[length - 1] = 1;
}
else
{
dp[length - 1] = 0;
}
for(int start = length - 2;start >= 0;start--)
{
if(s[start] == '0')
{
dp[start] = 0;
continue;
}
dp[start] = dp[start + 1];
profix = stoi(s.substr(start,2));
if(profix <= 26)
{
dp[start] = dp[start] + dp[start + 2];
}
}
return dp[0];
}
};
- 进一步改进后的DP解法
class Solution
{
public:
int numDecodings(string s)
{
int length = s.length();
int startnum = 0; //dp[start]的值
int start1 = 0; //dp[start + 1]
int start2 = 0; //dp[start + 2]
int profix = 0;
start2 = 1;
if (s[length - 1] != '0')
{
start1 = 1;
}
else
{
start1 = 0;
}
startnum = start1;
for (int start = length - 2; start >= 0; start--)
{
if (s[start] == '0')
{
startnum = 0;
start2 = start1;
start1 = startnum;
continue;
}
startnum = start1;
profix = stoi(s.substr(start, 2));
if (profix <= 26)
{
startnum = startnum + start2;
}
start2 = start1;
start1 = startnum;
}
return startnum;
}
};
这次只需要线性空间的内存即可做到。