SHEIN 2021.09.22 笔试题

题目描述

一条包含字母 A-Z 的消息通过以下方式进行了编码：
'a' -> 1
'b' -> 2
...
'z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

分析设计

这是LeetCode上的原题，很显然是动态规划的题目。
dp[i]表示到第i位时的编码总数
这需要考虑多种情况：
1、当s[i]=='0'时，如果s[i-1]=='1'或s[i-1]=='2'，dp[i]=dp[i-2]，否则直接返回0；
2、当s[i-1]=='1'时，如果s[i]>='1'且s[i]<='9'，dp[i]=dp[i-1]+dp[i-2]；
3、当s[i-1]=='2'时，如果s[i]>='1'且s[i]<='6'，dp[i]=dp[i-1]+dp[i-2]；
4、当然，以上1、2、3的情况是要i>=2的前提下，如果i==1，则第1种情况返回0；第2、3种情况dp[1]=1。

代码实现

class Solution{
    public int getCount(String s){
        int n = s.length();
        char[] ch = s.toCharArray();
        if(ch[0] == '0'){
            return 0;
        }
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i = 1; i < n; ++i){
            if(i == 1){
                if(c[i] == '0'){
                    dp[i] = 1;
                }
                else if(c[i - 1] == '1' && c[i] >= '1' && c[i] <= '9'){
                    dp[i] = 2;
                }
                else if(c[i - 1] == '2' && c[i] >= '1' && c[i] <= '6'){
                    dp[i] = 2;
                }
                else{
                    dp[i] = 1;
                }
            }
            else{
                if(c[i] == '0' && (c[i - 1] == '0' || c[i - 1] >= '3')){
                    return 0;
                }
                else if(c[i] == '0'){
                    dp[i] = dp[i - 2];
                }
                else if(c[i - 1] == '1' && c[i] >= '1' && c[i] <= '9'){
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
                else if(c[i - 1] == '2' && c[i] >= '1' && c[i] <= '6'){
                    dp[i] = dp[i - 1] + dp[i - 2];
                }
                else{
                    dp[i] = dp[i - 1];
                }
            }
        }
        return dp[n - 1];
    }
}