欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 91. Decode Ways(解码方法)

程序员文章站 2022-07-05 16:02:39
...
一条包含字母 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. 每次递进,可以选取一个数也可以选取两个数
  3. dp[i] = dp[i-1] + dp[i-2] 要判断条件
   public int numDecodings(String s) {
        if(s == null || s.length() <= 0) return 0;

        if(s.length() == 1) {
            if(s.charAt(0) >= '1' && s.charAt(0) <= '9') {
                return 1;
            }
            else {
                return 0;
            }
        }

        //dp[i]表示:数组下标处为i时的解码总数
        int[] dp = new int[s.length()];

        //dp[0]:只有一个字符时
        if(s.charAt(0) == '0') {
            dp[0] = 0;
        }
        else {
            dp[0] = 1;
        }

        //dp[1]:只有两个字符时
        if(s.charAt(0) == '1') {
            dp[1] += 1;
        }
        else if(s.charAt(0) == '2' && s.charAt(1) >= '0' && s.charAt(1) <= '6') {
            dp[1] += 1;
        }
        if(s.charAt(1) >= '1' && s.charAt(0) != '0') {
            dp[1] += 1;
        }


        for(int i = 2; i < s.length(); i ++) {
            if(s.charAt(i - 1) == '1') {
                dp[i] += dp[i - 2];
            }
            else if(s.charAt(i - 1) == '2' && s.charAt(i) >= '0' && s.charAt(i) <= '6') {
                dp[i] += dp[i - 2];
            }

            if(s.charAt(i) != '0') {
                dp[i] += dp[i - 1];
            }
        }

        return dp[s.length() - 1];


    }