首页 > 代码库 > leetcode[90] Decode Ways

leetcode[90] Decode Ways

题目:如下对应关系

‘A‘ -> 1

‘B‘ -> 2

...

‘Z’ -> 26

现在给定一个字符串,返回有多少种解码可能。例如:Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).

思路:动态规划。

dp[i]表示s[0,...,i-1]的种数。

那么dp[i]和dp[i-1]存在什么关系呢。

我们设singleVal为dp[i-1]所有可能组合的最后一个数字,且该数字小于10,singleCnt为dp[i-1]的最后一个数字为小于10的种数。

例如对于“1323”的组合为:

1,3,2,3

13,2,3

1,3,23

13,23

这是singleVal为3,singleCnt为2,如果再加入一个4,只要在前面的基础上加一个逗号,再加加入的值

1,3,2,3,4

13,2,3,4

1,3,23,4

13,23,4

再考虑之前单一的数字和加入的数字是否可能组合,因为单一的val是3,加入的是4,组合后34是不合法的。所以此时dp[i] = dp[i-1].

如果我们上面说的单一的数和加入的数的组合是合法的话,dp[i] = dp[i-1] + singleCnt; 再更新singleCnt为dp[i-1], singleVal为新加入的值。

主体部分就确定了。

那么如果当前加入的数字为0,只有当singleCnt大于零,且singleVal<=2才可能有10和20的组合可能,否则就直接返回0.

class Solution {public:int numDecodings(string s){    int len = s.size();    if (len == 0 || s[0] == 0) return 0;    int singleVal = s[0] - 0;    int singleCnt = 1;    vector<int> dp(len);    dp[0] = 1;    for (int i = 1; i < len; ++i)    {        if (s[i] == 0)        {            if (singleCnt != 0 && singleVal <= 2)            {                dp[i] = singleCnt;                 singleCnt = 0;                singleVal = 0;                continue;            }            else                 return 0;        }        if (singleVal == 1 || singleVal == 2 && s[i] <= 6)        {            dp[i] = dp[i - 1] + singleCnt;            singleCnt = dp[i - 1];            singleVal = s[i] - 0;        }        else        {            dp[i] = dp[i - 1];hh            singleCnt = dp[i - 1];            singleVal = s[i] - 0;        }    }    return dp[len - 1];}};

如上是我的做法,我还看了别人的做法:

  • 初始条件:dp[0] = 1, dp[1] = (s[0] == ‘0‘) ? 0 : 1
  • dp[i] = ( s[i-1] == 0 ? 0 : dp[i-1] ) + ( s[i-2,i-1]可以表示字母 ? dp[i-2] : 0 ), 其中第一个分量是把s[0...i-1]末尾一个数字当做一个字母来考虑,第二个分量是把s[0...i-1]末尾两个数字当做一个字母来考虑

代码如下:

class Solution {public:    int numDecodings(string s) {        // IMPORTANT: Please reset any member data you declared, as        // the same Solution instance will be reused for each test case.        //注意处理字符串中字符为0的情况        int len = s.size();        if(len == 0)return 0;        int dp[len+1];//dp[i]表示s[0...i-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-2];        }        return dp[len];    }};

 

leetcode[90] Decode Ways