美文网首页
解码方法 -dp

解码方法 -dp

作者: fdsun | 来源:发表于2020-06-04 10:06 被阅读0次

有一个消息包含A-Z通过以下规则编码

'A' -> 1
'B' -> 2
...
'Z' -> 26
现在给你一个加密过后的消息,问有几种解码的方式

样例
样例 1:

输入: "12"
输出: 2
解释: 它可以被解码为 AB (1 2) 或 L (12).
样例 2:

输入: "10"
输出: 1
注意事项
我们不能解码空串,因此若消息为空,你应该返回0。
消息的长度 n ≤ 100

    /**
     * @param s: a string,  encoded message
     * @return: an integer, the number of ways decoding
     */
    public static int numDecodings(String s) {
        // write your code here
        int n = s.length();
        if (n == 0) {
            return 0;
        }
        char[] chars = s.toCharArray();

        int[] f = new int[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            f[i] = 0;
            if (chars[i - 1] > '0' && chars[i - 1] <= '9') {
                f[i] += f[i - 1];
            }

            if (i > 1) {
                int j = 10 * (chars[i - 2] - '0') + (chars[i - 1] - '0');
                if (j >= 10 && j <= 26) {
                    f[i] += f[i - 2];
                }
            }
        }
        return f[n];
    }

相关文章

  • 91 Decode Ways

    将数字解码为字母可能的解码方法,动态规划求解,faster than 98%dp[i] = dp[i - 1] +...

  • 解码方法 -dp

    有一个消息包含A-Z通过以下规则编码 'A' -> 1'B' -> 2...'Z' -> 26现在给你一个加密过后...

  • LeetCode之Unique Paths(Kotlin)

    问题: 方法:经典的动态规划问题,dp[i][j] = dp[i-1][j] + dp[i][j-1],然后dp遍...

  • golang 接收输入流 AesECB解密

    解码方法 接收输入流并解码

  • px、dp、sp转换And屏幕相关信息获取工具类

    1、px、dp、sp相互转换方法 2、屏幕宽高px dp获取方法 3、屏幕密度 dpi获取方法

  • LeetCode-91-解码方法

    LeetCode-91-解码方法 91. 解码方法[https://leetcode-cn.com/problem...

  • 力扣 91 解码方法

    题意:给定一个字符串,里边是0-9的字符,数字的组合解码成a-z,求它的所有解码组合 思路:设一个dp数组,来记录...

  • 292. Nim Game

    key tips: 尝试dp方法,递推 分析轮次,寻找必然失败的stone number 算法 dp 归纳法

  • 小知识点

    js 中用于解码和加码的方法解码:dencodeURIComponent( url )加码:encodeURICo...

  • 解码方法

    一条包含字母 A-Z 的消息通过以下方式进行了编码: 给定一个只包含数字的非空字符串,请计算解码方法的总数。 示例...

网友评论

      本文标题:解码方法 -dp

      本文链接:https://www.haomeiwen.com/subject/eczwzhtx.html