把数字翻译成字符串
# 📃 题目描述
题目链接:
# 🔔 解题思路
dp[i] 表示字符串 nums 中以 i
个位置结尾的前缀字符串的解码种数,例如 nums = "123", 此时dp[0]=1,dp[1]=2,dp[2]=3
- 当前字符不等于 0 的时候, dp[i] = dp[i-1], 此时将当前位置的一个字符译码
- 当前字符+前一个字符,记为num, 如果 10<=num<=26,此时符合两个合并一起译码的条件,dp[i] = dp[i - 2]
总的来说,其实这道题目很像爬楼梯,一次能爬一层和爬两层,只是爬的过程中增加了一些限定条件,只要将这些限定条件屡清楚则可以完全搞懂这类题目~
import java.util.*;
public class Solution {
/**
* 解码
* @param nums string字符串 数字串
* @return int整型
*/
public int solve (String nums) {
if (nums == null || nums.length() == 0 || nums.charAt(0) == '0') {
return 0;
}
int n = nums.length();
// dp[i] 表示 nums[0...i] 有多少种译码结果
int[] dp = new int[n];
dp[0] = 1;
for (int i = 1; i < n; i ++) {
// 1. 最基本的, nums[i] 单独编码
if (nums.charAt(i) != '0') {
dp[i] = dp[i - 1];
}
// 2. nums[i] 和 nums[i - 1] 共同编码
int num = (nums.charAt(i - 1) - '0') * 10 + (nums.charAt(i) - '0');
if (num >= 10 && num <= 26) {
// 处理下边界情况
if (i == 1) {
dp[i] += 1;
}
else {
dp[i] += dp[i - 2];
}
}
}
return dp[n - 1];
}
}
# 💥 复杂度分析
- 空间复杂度:
- 时间复杂度:
🎁 公众号

各位小伙伴大家好呀,叫我小牛肉就行,目前在读东南大学硕士,上方扫码关注公众号「飞天小牛肉」,与你分享我的成长历程与技术感悟~
帮助小牛肉改善此页面 (opens new window)
Last Updated: 2023/02/16, 11:27:10