厦门市建设工程交易中心网站,营销策划方案怎么写,wordpress前台加速,搜索栏在wordpress菜单上位置91. 解码方法
一条包含字母 A-Z 的消息通过以下映射进行了 编码 #xff1a; ‘A’ - “1” ‘B’ - “2” … ‘Z’ - “26” 要 解码 已编码的消息#xff0c;所有数字必须基于上述映射的方法#xff0c;反向映射回字母#xff08;可能有多种方法#xff0…91. 解码方法
一条包含字母 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。 示例 2 输入s “226” 输出3 解释它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。 示例 3 输入s “06” 输出0 解释“06” 无法映射到 “F” 因为存在前导零“6” 和 “06” 并不等价。 提示
1 s.length 100s 只包含数字并且可能包含前导零。
思路(动态规划)
这道题不要往复杂了想其实一共就是两种情况一次解码一个字符和一次解码两个字符dp[i] 就等于这两种情况之和。
dp数组的含义dp[i] 为前 i 个子字符串 (即从 0 ~ i-1) 一共有多少种编码方式。
递推公式为 dp[i]dp[i−1]dp[i−2]dp[i] dp[i - 1] dp[i - 2]dp[i]dp[i−1]dp[i−2]
特别需要注意的是
如果 s[i] 0 不能单独解码只能和前一个组合解码前一个 s[i-1] 必须是 1 或者 2否则超出范围无法解码。 如果可以前一个字符s[i-1]组合解码则s[i-1]就不能和s[i-2]在组合了此时dp[i] dp[i -2]如果不能组合解码则该字符串无法解码。 如果 s[i] 不为0则肯定可以单独解码能否组合解码还要判断组合码是否超出边界或者无法映射。 如果 s[i] 可以组合解码则: dp[i] dp[i - 1] dp[i - 2] ;不能组合解码则 dp[i] dp[i - 1] 。
代码(Java)
public class DecodingWays {public static void main(String[] args) {// TODO Auto-generated method stubString s 226;System.out.println(numDecodings(s));}public static int numDecodings(String s) {int n s.length();if(s.charAt(0) 0)return 0;int []dp new int[n 1];dp[0] dp[1] 1;for(int i 1; i n; i) {if(s.charAt(i) 0 (s.charAt(i - 1) 1 || s.charAt(i - 1) 2)) {dp[i 1] dp[i - 1];}else if(s.charAt(i) 0) {return 0;}else if(Integer.valueOf(s.substring(i - 1,i 1)) 27 Integer.valueOf(s.substring(i - 1,i 1)) 10) {dp[i 1] dp[i] dp[i - 1];}else {dp[i 1] dp[i];}}return dp[n];}
}运行结果 复杂度分析 时间复杂度O(n)其中 n 是字符串 s 的长度。 空间复杂度O(n)。使用数组进行状态转移其中 n 是字符串 s 的长度
注仅供学习参考
题目来源力扣。
