91、解码方法

leetcode

Created At : 2020-07-26 00:19

Count:884 Views 👀 :

示例 1:
示例 2:

一条包含字母 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地时候才可能有两者种解
从后往前遍历
递归实现

class Solution {
    public int numDecodings(String s) {
        char[] chs = s.toCharArray();
        return getNum(chs,0);
    }
    
    private int getNum(char[] chs,int index) {
        // 递归判断
        if (index == chs.length) {
            return 1;
        }
        // 不存在0，或者以0开头地字母码
        if (chs[index] == '0') {
            return 0;
        }
        // 每次只考虑1-9
        int count1 = getNum(chs,index+1);
        // 处理两位数字母码
        int count2 = 0;
        if (index < chs.length - 1) {
            // int s1 = (chs[index] - '0')*10;
            // s1 += chs[index+1] - '0';
            // if (s1 <= 26){
            //     count2 = getNum(chs,index+2);
            // }
            /// 或者
            if (chs[index] - '0' == 1 || (chs[index] - '0' == 2 && chs[index + 1] - '0' < 7) ) {
                count2 = getNum(chs,index+2);
            }
        }
        return count1 + count2;
    }
}

动态规划
- dp[i] 表示遍历到第i个字母地时候总的可解码方法的数量
- 递推公式：
  - dp[i] = dp[i] s[i] == 0 或者 s[i]s[i+1]>26
  - dp[i] = dp[i+1] + dp[i+2] s[i]s[i+1]>26

// 传统dp数组存储状态
public int numDecodings(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }
    int len = s.length();

    int[] dp = new int[len+1];
    // 自顶而下
    dp[len] = 1;
    // len - 1
    if (s.charAt(len - 1) == '0') {
        dp[len - 1] = 0;
    } else {
        dp[len - 1] = 1;
    }

    for (int i = len - 2;i >= 0;i--) {
        // 没有0开头的解码
        if (s.charAt(i) == '0') {
            dp[i] = 0;
            continue;
        }
        // 是否可以取两位数
        if (s.charAt(i)  == '1' || (s.charAt(i) == '2' && s.charAt(i+1) < '7')) {
            dp[i] = dp[i+1] + dp[i+2];
        } else { // 不可以
            dp[i] = dp[i+1];
        }
    }
    return dp[0];
}

// 变量存储之前的状态，空间复杂度O(1)
// pre 存贮 i+2 处的结果
// res
public  int numDecodings(String s) {
    if (s == null || s.length() == 0) {
        return 0;
    }

    int len = s.length();

    int pre = 1;
    int cur = 0;
    if (s.charAt(len - 1) != '0') {
        cur = 1;
    }
    for (int i = len -2;i >= 0;i--) {
        if (s.charAt(i) == '0') {
            pre = cur;
            cur = 0;
            continue;
        }

        if (s.charAt(i)  == '1' || (s.charAt(i) == '2' && s.charAt(i+1) < '7')){
            cur += pre;
            pre = cur-pre;
        } else {
            pre = cur;
        }
    }
    return cur;
}

// C++ 实现 自下而上
int numDecodings(string s) {
    if (s[0] == '0') return 0;
    int pre = 1,curr = 1;// dp[-1] = dp[0] = 1;
    for (int i = 1;i < s.size();i++) {
        int tmp = curr;
        if (s[i] == '0') {
            if (s[i - 1] == '1' || s[i - 1] == '2') curr = pre;
            else return 0;
        } else if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] >= '1' && s[i] <= '6')) {
            curr = curr + pre;
        }
        pre = tmp;
    }
    return curr;
}
// Java 自下而上
class Solution {
    public  int numDecodings(String s) {
        if (s.charAt(0) == '0') {
            return 0;
        }

        int len = s.length();

        int pre = 1;
        int cur = 1;

        for (int i = 1;i < len;i++) {
            int tmp = cur;
            if (s.charAt(i) == '0') {
                if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2') {
                    cur = pre;
                } else {
                    return 0;
                }
            } else if (s.charAt(i - 1)  == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) < '7')){
                cur = cur + pre;
            }
            pre = tmp;
        }
        return cur;
    }
}

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com