LeetCode 91. Decode Ways

思路

警告：千万注意’0’这个异类，当然了还有空输入:(。
其实也是个动态规划?的问题，有点像那个走楼梯的题
当前能decode的方法数与之前的两种状态有关，就是

• 判断当前的字母s[i]能不能单个decode，如果可以，那方法数就要加上解码s[i-1]时的方法数，如果不能解那就不加；
• 判断两个字符s[i-1]s[i]的组合能不能解码（就是在不在10-26的范围内），如果可以，拿加上解码s[i-2]时的方法数；

所以事实上只要保存s[i],s[i-1]两个方法数的结果就行，我的代码空间复杂度还比较大，但是不想改了。

代码

class Solution {
public:
    bool isLegalBiChar(char m, char n){
        // is "mn" a legal word?
        if(m != '1' && m != '2')
            return false;
        if(m == '2'){
            if(n > '6')
                return false;
        }
        return true;
    }
    int numDecodings(string s) {
        if(s.empty() || s[0]=='0')
            return 0;
        int* decodeWays = new int[s.size()];
        //be care of '0's
        decodeWays[0] = 1;
        for(int i=1; i<s.size(); i++){
            int ways = 0;
            if(s[i] > '0' && s[i] <= '9'){
                ways += decodeWays[i-1];
            }
            if(isLegalBiChar(s[i-1], s[i])){
                if(i<2)
                    ways += 1;
                else
                    ways += decodeWays[i-2];
            }
            decodeWays[i] = ways;
        }
        return decodeWays[s.size()-1];
    }
};