当前位置：首页 > news >正文

左神算法之数字字符串解码方案计数算法

news 2025/6/27 22:01:09

文章目录

数字解码为字母的方案计数
- 问题理解
- 解题思路
- Java实现
- 代码解析
- 测试用例
- 总结

数字解码为字母的方案计数

问题理解

给定一个数字字符串，我们需要计算它可以被解码为字母字符串的所有可能方式。解码规则为：

数字1对应字母’a’
数字2对应字母’b’
…
数字26对应字母’z’

例如，"12258"有5种解码方式：

1 2 2 5 8 → “abbeh”
1 2 25 8 → “abyh”
1 22 5 8 → “aveh”
12 2 5 8 → “lbeh”
12 25 8 → “lyh”

解题思路

这个问题可以使用动态规划来解决，关键在于如何处理数字的组合方式：

基本情况：
- 空字符串有1种解码方式（即空字符串）
- 单个数字字符（非’0’）有1种解码方式
递推关系：
- 当前数字可以单独解码（1-9）
- 当前数字和前一个数字可以组合解码（10-26）
边界条件：
- 数字’0’不能单独解码
- 以’0’开头的字符串无法解码

Java实现

public class DecodeWays {public static int numDecodings(String s) {if (s == null || s.length() == 0) {return 0;}int n = s.length();int[] dp = new int[n + 1];dp[0] = 1; // 空字符串有1种解码方式dp[1] = s.charAt(0) == '0' ? 0 : 1; // 第一个字符的解码方式for (int i = 2; i <= n; i++) {// 检查单个数字int oneDigit = Integer.parseInt(s.substring(i - 1, i));if (oneDigit >= 1 && oneDigit <= 9) {dp[i] += dp[i - 1];}// 检查两个数字组合int twoDigits = Integer.parseInt(s.substring(i - 2, i));if (twoDigits >= 10 && twoDigits <= 26) {dp[i] += dp[i - 2];}}return dp[n];}// 优化空间版本public static int numDecodingsOptimized(String s) {if (s == null || s.length() == 0 || s.charAt(0) == '0') {return 0;}int prev1 = 1; // dp[i-1]int prev2 = 1; // dp[i-2]for (int i = 1; i < s.length(); i++) {int current = 0;// 检查单个数字if (s.charAt(i) != '0') {current += prev1;}// 检查两个数字组合int twoDigits = Integer.parseInt(s.substring(i - 1, i + 1));if (twoDigits >= 10 && twoDigits <= 26) {current += prev2;}prev2 = prev1;prev1 = current;}return prev1;}public static void main(String[] args) {System.out.println(numDecodings("12258")); // 输出5System.out.println(numDecodings("226"));   // 输出3System.out.println(numDecodings("06"));    // 输出0System.out.println(numDecodingsOptimized("12258")); // 输出5System.out.println(numDecodingsOptimized("226"));   // 输出3System.out.println(numDecodingsOptimized("06"));    // 输出0}
}

代码解析

基础动态规划版本：
- 使用dp数组存储中间结果，dp[i]表示前i个字符的解码方式数
- 检查单个数字（1-9）和两个数字组合（10-26）的可能性
- 时间复杂度O(n)，空间复杂度O(n)
优化空间版本：
- 仅使用两个变量prev1和prev2代替整个dp数组
- 每次迭代更新当前值并滚动更新前两个状态
- 时间复杂度O(n)，空间复杂度O(1)

测试用例

public static void main(String[] args) {// 常规测试System.out.println(numDecodings("12"));     // 输出2 ("AB"或"L")System.out.println(numDecodings("226"));   // 输出3// 边界测试System.out.println(numDecodings("0"));     // 输出0System.out.println(numDecodings("10"));    // 输出1System.out.println(numDecodings("100"));   // 输出0// 大数测试System.out.println(numDecodings("1111111111111111111111111111"));  // 输出317811
}