写点什么

【LeetCode】解码方法 Java 题解

用户头像
HQ数字卡
关注
发布于: 2021 年 04 月 21 日

题目描述

一条包含字母 A-Z 的消息通过以下映射进行了 编码 :


'A' -> 1'B' -> 2...'Z' -> 26 要 解码 已编码的消息,所有数字必须基于上述映射的方法,反向映射回字母(可能有多种方法)。例如,"11106" 可以映射为:


"AAJF" ,将消息分组为 (1 1 10 6)"KJF" ,将消息分组为 (11 10 6)注意,消息不能分组为  (1 11 06) ,因为 "06" 不能映射为 "F" ,这是由于 "6" 和 "06" 在映射中并不等价。


给你一个只含数字的 非空 字符串 s ,请计算并返回 解码 方法的 总数 。


题目数据保证答案肯定是一个 32 位 的整数。


示例 1:


输入:s = "12"输出:2解释:它可以解码为 "AB"(1 2)或者 "L"(12)。
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/decode-ways
复制代码

代码

public class DayCode {    public static void main(String[] args) {        String s = "12";        int ans = new DayCode().numDecodings(s);        System.out.println("ans is " + ans);    }
/** * 时间复杂度 O(n) * 空间复杂度 O(n) * @param s * @return */ public int numDecodings(String s) { int n = s.length(); int[] dp = new int[n + 1]; dp[0] = 1; for (int i = 1; i <= n; i++) { if (s.charAt(i - 1) != '0') { dp[i] += dp[i - 1]; } if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0')) <= 26) { dp[i] += dp[i - 2]; } } return dp[n]; }}
复制代码

总结

  • 这个题目是求解个数问题,动态规划是比较好的解决方案。

  • 状态转移方程,根据题目提示,考虑单个字符的解码方式,两个字符的解码方式,分为 2 种情况讨论。

  • 坚持每日一题,加油!

发布于: 2021 年 04 月 21 日阅读数: 12
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】解码方法Java题解