算法面试真题详解:解码方法-阿里云开发者社区

开发者社区> 算法编程> 正文

算法面试真题详解:解码方法

简介: 算法面试真题详解:解码方法

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

  • 我们不能解码空串,因此若消息为空,你应该返回0。
  • 消息的长度 n≤100

在线评测地址:领扣题库官网

样例 1:

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

样例 2:

输入: "10"
输出: 1

算法:动态规划(dp)

算法思路

  • 对于一段编码s,设他有x种解码,如果在s后面加上一个个位数,那么获得的编码就拥有s的这x种解码方式(不仅限于这x种);如果在后面加上一个小于等于26的两位数,那么同理可得,获得的编码就拥有s的这x种解码方式(不仅限于这x种)。
  • 因此我们可以用动态规划的方式来解决这个问题
    代码思路
  • 状态:dp[i]表示字符串的前i位解码有多少种解码方式
  • 初始化:dp[0] = dp[1] = 1,dp数组其他值均为0,
  • 状态转移方程

    • 若s[i - 1]表示的数是1到9,dp[i] += dp[i - 1]
    • 若s[i - 2]和s[i - 1]表示的数是10到26,dp[i] += dp[i - 2]
    • 若上述两种情况都不满足,直接返回答案0
  • 如果s以 '0' 开头, 则直接返回0

复杂度分析

N表示字符串长度

  • 空间复杂度:O(N) 可以用滚存优化到O(1)
  • 时间复杂度:O(N)
public class Solution {
    /**
     * @param s: a string,  encoded message
     * @return: an integer, the number of ways decoding
     */
    public int numDecodings(String s) {
        //如果s以 '0' 开头, 则直接返回0
        if (s.length() == 0 || s.charAt(0) == '0') {
            return 0;
        }
        //数组初值均为0,dp[0] = dp[1] = 1
        //dp[i]表示字符串的前i位解码有多少种解码方式
        int n = s.length();
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 1;
        for (int i = 2; i <= n; i++) {
            //若s[i - 1]表示的数是1到9
            if (s.charAt(i - 1) != '0') {
                dp[i] += dp[i - 1];
            }
            //若s[i - 2]和s[i - 1]表示的数是10到26
            if (s.charAt(i - 2) != '0' && (s.charAt(i - 2) - '0') * 10 + s.charAt(i - 1) - '0' <= 26) {
                dp[i] += dp[i-2];
            }
            //若上述两种情况都不满足,直接返回答案0
            if (dp[i] == 0) {
                return 0;
            }
        }
        return dp[n];
    }
}

更多题解参考:九章官网solution

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

分享:
算法编程
使用钉钉扫一扫加入圈子
+ 订阅

开发者社区在线编程频道官方技术圈。包含算法资源更新,周赛动态,每日一题互动。

官方博客
链接