leetCode.91. 解码方法

题目思路

题解

class Solution {
public:
    int numDecodings(string s) {
        int n = s.size();
        // dp 中f[0]一般不做使用，只是存一个初值1，表示默认由一种方案
        s = ' ' + s;
        vector<int> f( n + 1 );

        f[0] = 1;
        for ( int i = 1; i <= n; ++ i ) {
            // 一位数的判断
            if ( s[i] >= '1' && s[i] <= '9' ) f[i] += f[i - 1];
            // f[i - 1]的判断（两位数的判断必须保证 i > 1才会出现两位数 ）
            if ( i > 1 ) {
                int t = (s[i - 1] - '0') * 10 + (s[i] - '0');
                if ( t >= 10 && t <= 26 ) {
                    f[i] += f[i - 2];
                }
            }
        }

        return f[n];
    }
};