leetcode面试准备:DecodeWays-创新互联

1 题目

A message containing letters from A-Z is being encoded to numbers using the following mapping:

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

Given an encoded message containing digits, determine the total number of ways to decode it.

For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.

接口:public int numDecodings(String s);

2 思路

一维动态规划,偷懒了，照搬博文。
分析：需要注意的是，如果序列中有不能匹配的0，那么解码方法是0，比如序列012 、100（第二个0可以和1组成10，第三个0不能匹配）。

• 递归的解法很容易，但是大集合会超时。转换成动态规划的方法，假设dp[i]表示序列s[0...i-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]末尾两个数字当做一个字母来考虑

复杂度: Time O(n); Space O(n)

3 代码

        public int numDecodings(String s) {        // 1.初始化
        final int len = s.length();        if (len == 0)            return 0;        int[] dp = new int[len + 1];
        dp[0] = 1;        if (s.charAt(0) != '0')
            dp[1] = 1;        else
            dp[1] = 0;        // 2.一维DP方程
        for (int i = 2; i <= len; i++) {            if (s.charAt(i - 1) != '0')
                dp[i] = dp[i - 1];            else
                dp[i] = 0;            if (s.charAt(i - 2) == '1'
                    || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))
                dp[i] += dp[i - 2];
        }        return dp[len];
    }

4 总结

写递归的解法

新航道雅思

另外有需要云服务器可以了解下创新互联scvps.cn，海内外云服务器15元起步，三天无理由+7*72小时售后在线，公司持有idc许可证，提供“云服务器、裸金属服务器、高防服务器、香港服务器、美国服务器、虚拟主机、免备案服务器”等云主机租用服务以及企业上云的综合解决方案，具有“安全稳定、简单易用、服务可用性高、性价比高”等特点与优势，专为企业上云打造定制，能够满足用户丰富、多元化的应用场景需求。