Leetcode 91. Decode Ways

原题地址

https://leetcode.com/problems/decode-ways/description/

题意

将A-Z用数字表示

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

给定一串数字组成的string，求出有几种不同的翻译方式。

思路

dp[i] 表示到第i个字符的位置有几种不同的翻译方式。
dp[i+1]时则只需要考虑 string[i+1]是否能与string[i]结合，然后分别在dp[i]的基础上加上不同的值。

然而还是太naive，忘记考虑 ‘0’ 的存在了。本题‘0’只能跟在其他数字之后，而不能组成‘0X’这样的形式。
打码的时候基于‘0’的很多情况都没考虑到，都是碰到测试样例不过看样例才发觉哪里错了，然后修修补补，因此代码写得比较不忍卒读。
有空的时候会重新写一遍的。

代码

#include <iostream>
#include <string>
#include <stdlib.h>     /* atoi */

using namespace std;

class Solution {
public:
    int numDecodings(string s) {
        if (s.size() == 0) return 0;
        if (s.size() == 1) {
            if (s[0] == '0') return 0;
            else return 1;
        }
        if (s.size() == 2 ) {
            if (s[0] == '0') return 0;
            if(s[1]=='0'){
                if ( atoi(s.c_str()) <= 26) {
                    return 1;
                } else {
                    return 0;
                }                   
            }else{
                if ( atoi(s.c_str()) <= 26) {
                    return 2;
                } else {
                    return 1;
                }   
            }
        }
        int n = s.size();
        int dp[n + 1];
        for (int i = 0; i < n; i++) {
            if (s[0] == '0') return 0;
            if (s[i] == '0' && (atoi(s.substr(i - 1, 2).c_str()) > 26 || atoi(s.substr(i - 1, 2).c_str()) == 0)) return 0;
        }
        dp[1] = 1;
        if (s[1] == '0') {
            dp[2] = 1;
            cout << "a" << endl;
        } else if (atoi(s.substr(0, 2).c_str()) <= 26) {
            dp[2] = 2;
        } else {
            dp[2] = 1;
        }
        for (int i = 2; i < n ; i++) {
            if ( s[i] == '0') {
                if (atoi(s.substr(i - 1, 2).c_str()) > 20) {
                    // cout<<s.substr(i - 1, 2)<<endl;
                    return 0;
                } else {
                    dp[i+1] = dp[i - 1];
                }
            } else if(s[i-1]=='0'){
                dp[i+1]=dp[i-1];
            } else if ( atoi(s.substr(i - 1, 2).c_str()) <= 26) {
                dp[i+1] = dp[i ] +dp[i-1];
            } else {
                dp[i+1] = dp[i ];
            }
        }
        for(int i =1;i<=n;i++){
            cout<<dp[i]<<endl;
        }
        return dp[n];
    }
};