LeetCode 91. 解码方法 Java

91. 解码方法

难度中等412收藏分享切换为英文关注反馈

一条包含字母 A-Z 的消息通过以下方式进行了编码：

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

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

解题思路：首先要想到是斐波那契数列，当当前位置可以和前面字符结合，如前面是1，当前是2。 12可以拆开也可以结合。因此

遍历到当前Fn=Fn-1+Fn-2，但是如果不可以和前面字符结合，如2，7，当前Fn=Fn-1，Fn-1=Fn-2。

 

此外，就是要处理0，因为0决定了字符串合法与否，并且合法字符串的0一定会与前面的字符相结合，删除掉不会影响最终结果。

class Solution {
    public static int numDecodings(String s) {
        int pre1 = 1;
        int pre2 = 1;
        
        //不合法字符串 如30
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)==48){
                if(i==0||s.charAt(i-1)>50||s.charAt(i-1)==48){
                    return 0;
                }
            }
        }
        //消0，0比较特殊，因为0一定会和前一位配对，该字母不影响结果。
        String s1 = new String();
        int judge=0;
        for (int i = 0; i < s.length() - 1; i++) {
            if (s.charAt(i + 1) != '0') {
                s1+=String.valueOf(s.charAt(i));
            } else {
                judge=1;
                i++;
            }
        }
        if(s.charAt(s.length()-1)!='0') {
            s1+=s.charAt(s.length()-1);
        }
        if (s1.length() == 0||s1.length()==1 ) {
            return Math.max(judge,s1.length());
        }

        //变形的斐波那契数列
        for(int i=1;i<s1.length();i++){
            int tmp=0;
            if(pair(s1.charAt(i-1),s1.charAt(i))){
                tmp=pre1+pre2;
                pre1=pre2;
                pre2=tmp;
            }
            else{
                pre1=pre2;
            }
        }
        return pre2;
    }
    public static boolean pair(char a,char b){
        if(a==50&&b<55){
            return true;
        }
        if(Integer.valueOf(a)==49) {
            return true;
        }
        return false;
    }
}