[数据结构与算法]【Lintcode】676. Decode Ways II

题目地址：

https://www.lintcode.com/problem/676/

对于一个只含英文大写字母的字符串$s$，其每个字母可以按照'A' -> 1, ..., 'Z' -> 26来编码。现在给定一个只含$0～9$与$?$的字符串$t$，$?$可以视为$1～9$的任意一种。问其有多少种解码方式。答案模$10^9+7$返回。

思路是动态规划。设$f[k]$是$t$的前$k$个字母组成的前缀的解码方式数。那么可以分为两种情况，第一种是最后一个字母单独解码，另一种是最后两个字母一起解码（这需要$k\ge 2$才可以）。分类讨论即可。代码如下：

public class Solution {
    /**
     * @param s: a message being encoded
     * @return: an integer
     */
    public int numDecodings(String s) {
        // write your code here
        int n = s.length();
        long mod = (long) (1e9 + 7);
        long[] f = new long[n + 1];
        // 空串只能解码为空串
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            char ch = s.charAt(i - 1), prev = 0;
            if (i >= 2) {
                prev = s.charAt(i - 2);
            }
            
            if (ch == '*') {
                f[i] = (f[i] + 9 * f[i - 1]) % mod;
                
                if (i >= 2) {
                    if (prev == '1') {
                        f[i] = (f[i] + 9 * f[i - 2]) % mod;
                    } else if (prev == '2') {
                        f[i] = (f[i] + 6 * f[i - 2]) % mod;
                    } else if (prev == '*') {
                        f[i] = (f[i] + 15 * f[i - 2]) % mod;
                    }
                }
            } else {
                if (ch != '0') {
                    f[i] = (f[i] + f[i - 1]) % mod;
                }
                
                if (i >= 2) {
                    if (prev == '1') {
                        f[i] = (f[i] + f[i - 2]) % mod;
                    } else if (prev == '2') {
                        if (ch <= '6') {
                            f[i] = (f[i] + f[i - 2]) % mod;
                        }
                    } else if (prev == '*') {
                        if (ch <= '6') {
                            f[i] = (f[i] + 2 * f[i - 2]) % mod;
                        } else {
                            f[i] = (f[i] + f[i - 2]) % mod;
                        }
                    }
                }
            }
        }
        
        return (int) f[n];
    }
}

时空复杂度$O(l_t)$。