有一种将字母编码成数字的方式：'a'->1, 'b->2', ... , 'z->26'。
现在给一串数字，返回有多少种可能的译码结果
数据范围：字符串长度满足 
进阶：空间复杂度 %20)
，时间复杂度 )
[编程题]把数字翻译成字符串
dp + dfs
public class Solution {
int res = 0;
public int solve (String nums) {
// write code here
//dp
int len = nums.length();
if (len == 0 || nums.charAt(0) == '0') return 0;
int[] dp = new int[len+1];
dp[0] = 1;
for (int i=1;i<=len;++i){
char c = nums.charAt(i-1);
if (c != '0'){
dp[i] = dp[i-1];
}
if (i-2 >= 0){
int val = Integer.valueOf(nums.substring(i-2, i));
if (val >=10 && val <= 26){
dp[i] += dp[i-2];
}
}
}
return dp[len];
/*dfs(nums,0);
return res;*/
// dfs
/* private void dfs(String nums, int start) {
if(start >= nums.length()) {
res++;
return;
}
if(Integer.valueOf(nums.substring(start, start+1)) != 0)
dfs(nums,start+1);
if(start < nums.length()-1 && Integer.valueOf(nums.substring(start, start+2)) >= 10 && Integer.valueOf(nums.substring(start, start+2)) <= 26)
dfs(nums,start+2);*/
}
}
发表于 2021-06-21 11:33:53
回复(0)
public int solve (String nums) {
if(nums.length() == 0 || nums.equals("0")){
return 0;
}
int a=1,b=1;
for(int i=2;i<=nums.length();i++){
if(nums.charAt(i-1) == '0'){
b=0;
}
int sum=0;
String tmp = nums.substring(i-2,i);
if(tmp.compareTo("10")>=0 && tmp.compareTo("26")<=0){
sum = a+b;
}else{
sum = b;
}
a = b;
b = sum;
}
return b;
}
if(nums.length() == 0 || nums.equals("0")){
return 0;
}
int a=1,b=1;
for(int i=2;i<=nums.length();i++){
if(nums.charAt(i-1) == '0'){
b=0;
}
int sum=0;
String tmp = nums.substring(i-2,i);
if(tmp.compareTo("10")>=0 && tmp.compareTo("26")<=0){
sum = a+b;
}else{
sum = b;
}
a = b;
b = sum;
}
return b;
}
发表于 2021-04-29 15:41:55
回复(1)
class Solution {
public:
/**
* 解码
* @param nums string字符串 数字串
* @return int整型
*/
int solve(string nums) {
vector<int> dp(nums.size() +1,0);
dp[0] = 1;
dp[1] = nums[0] != '0'? 1 : 0;
for (int i = 2; i <= nums.size(); ++i)
{
dp[i] = (isZero(nums[i-1])? 0 : dp[i-1]) + (isOverThreshold(nums[i-2], nums[i-1])? dp[i-2] : 0);
}
return dp[nums.size()];
}
bool isZero(char const& a) const
{
return a == '0';
}
bool isOverThreshold(char const& a, char const& b) const
{
return a == '1' || (a == '2' && b <= '6');
}
};
public:
/**
* 解码
* @param nums string字符串 数字串
* @return int整型
*/
int solve(string nums) {
vector<int> dp(nums.size() +1,0);
dp[0] = 1;
dp[1] = nums[0] != '0'? 1 : 0;
for (int i = 2; i <= nums.size(); ++i)
{
dp[i] = (isZero(nums[i-1])? 0 : dp[i-1]) + (isOverThreshold(nums[i-2], nums[i-1])? dp[i-2] : 0);
}
return dp[nums.size()];
}
bool isZero(char const& a) const
{
return a == '0';
}
bool isOverThreshold(char const& a, char const& b) const
{
return a == '1' || (a == '2' && b <= '6');
}
};
发表于 2021-04-24 22:35:09
回复(0)
public class Solution {
public int solve(String nums) {
if (nums.isEmpty() || nums.charAt(0) == '0') {
return 0;
}
if (nums.length() == 1) {
return 1;
}
int[] dp = new int[nums.length()];
dp[0] = 1;
int x1 = getX(nums, 1);
if (x1 == 10 || x1 == 20) {
dp[1] = 1;
} else if (x1 <= 26 ) {
dp[1] = 2;
} else {
dp[1] = 1;
}
for (int n = 2; n < nums.length(); n++) {
int x = getX(nums, n);
if (x == 10 || x == 20) {
dp[n] = dp[n - 2];
} else if (x <= 26 && x > 10) {
dp[n] = dp[n - 1] + dp[n - 2];
} else if (x < 10 && x > 0) {
dp[n] = dp[n - 1];
} else if (x == 0) {
return 0;
} else {
dp[n] = dp[n - 1];
}
}
return dp[dp.length - 1];
}
private int getX(String nums, int i) {
return (nums.charAt(i - 1) - '0') * 10 + (nums.charAt(i) - '0');
}
}
public int solve(String nums) {
if (nums.isEmpty() || nums.charAt(0) == '0') {
return 0;
}
if (nums.length() == 1) {
return 1;
}
int[] dp = new int[nums.length()];
dp[0] = 1;
int x1 = getX(nums, 1);
if (x1 == 10 || x1 == 20) {
dp[1] = 1;
} else if (x1 <= 26 ) {
dp[1] = 2;
} else {
dp[1] = 1;
}
for (int n = 2; n < nums.length(); n++) {
int x = getX(nums, n);
if (x == 10 || x == 20) {
dp[n] = dp[n - 2];
} else if (x <= 26 && x > 10) {
dp[n] = dp[n - 1] + dp[n - 2];
} else if (x < 10 && x > 0) {
dp[n] = dp[n - 1];
} else if (x == 0) {
return 0;
} else {
dp[n] = dp[n - 1];
}
}
return dp[dp.length - 1];
}
private int getX(String nums, int i) {
return (nums.charAt(i - 1) - '0') * 10 + (nums.charAt(i) - '0');
}
}
发表于 2021-01-16 15:01:40
回复(0)
dp
class Solution {
public:
/**
* 解码
* @param nums string字符串 数字串
* @return int整型
*/
int solve(string nums) {
// write code here
string s=nums;
int n=s.size();
vector<int> dp(n+1, 0);
bool flag=true;
dp[1] = s[0]=='0'?0:1;
for(int i=2; i<=n; i++) {
if(s[i-1]=='0' && s[i-2]=='0') {
flag = false;
break;
}
if(s[i-1]=='0') dp[i] = i-2>0?dp[i-2]:1;
else if(s[i-2]=='0') dp[i] = dp[i-1];
else {
dp[i] += dp[i-1];
if(s[i-2]=='1' || (s[i-2]=='2' && s[i-1]<='6' && s[i-1]>='1')) dp[i] += i-2>0?dp[i-2]:1;
}
}
return flag?dp[n]:0;
}
};
发表于 2020-08-06 16:40:36
回复(1)
你说你改个力扣的题就改，考边界条件你倒是把题说清楚，弄得自己试错试半天，比如1102能不能分成11和02来解，100能不能算合法，全tm自己碰出来的，真想骂人这题做的。力扣没费多大劲想出来的这儿熬一晚上，垃圾牛客。
public class Solution {
/**
* 解码
* @param nums string字符串 数字串
* @return int整型
*/
public int solve (String nums) {
// 带条件的青蛙跳台阶
// 如果n位数和n-1位的数字组合而成的2位数在10-26闭区间中，f(n)=f(n-1)+f(n-2);
// 否则f(n)=f(n-1)
// 注意，有几个题干没说清楚的点在此补充：
// 0+个位数不能当个位数来使，比如1102只能拆成1/10/2不能拆成11/02
// 不能出现孤立0在末位的情况，比如100不能当成10/0处理，但010可以当成0/10处理
// 字符串“0”算作0种译法
if(nums.length()==0 || "0".equals(nums)){
return 0;
}
int a = 1;
int b = 1;
int sum = 1;
for(int i=1;i<nums.length();i++){
// 计算和前一个数组成2位数的值
int value = getValue(nums.charAt(i-1),nums.charAt(i));
// 很重要的一步操作
if(nums.charAt(i) == '0')
b = 0;
// 带条件的青蛙跳台阶
if(value>=10 && value <=26){
sum = a + b;
}
else{
sum = b;
}
a = b;
b = sum;
}
return sum;
}
public int getValue(char a, char b){
return Integer.parseInt(""+a+b);
}
}
发表于 2022-01-18 22:11:34
回复(6)
这道题主要是对0的处理，比如00这种是非法的，而10呢，则只有一种编码。
用dp[i]表示s[0,...,i-1]时的编码次数，那么：
如果s[i-1] == '0'，dp[i] = 0，否则dp[i] = dp[i-1];
接着再根据s[i-1]s[i-2]更新dp[i]：
如果s[i-1] == '1'，dp[i] += dp[i-2]
如果s[i-1] == '2'
> s[i] <= 6，dp[i] += dp[i-2]
class Solution {
public:
/**
* 解码
* @param nums string字符串 数字串
* @return int整型
*/
int solve(string nums) {
vector<int> dp(nums.size()+1);
if(nums.empty() || nums == "0") return 0;
dp[0] = 1;
for(int i = 1; i <= nums.size(); i++) {
dp[i] = nums[i-1] == '0' ? 0 : dp[i-1];
if((i > 1) && ((nums[i-2] == '1')
|| (nums[i-2] == '2' && nums[i-1] <= '6'))) {
dp[i] += dp[i-2];
}
}
return dp[nums.size()];
}
};
编辑于 2021-04-16 21:54:39
回复(2)
class Solution {
public:
/**
* 解码
* @param nums string字符串 数字串
* @return int整型
*/
int solve(string nums) {
// write code here
if (nums.empty() || nums == "0") return 0;
int n = nums.size();
vector<int> dp(n + 1, 0);
dp[0] = 1;
for (int i = 1; i <= n; ++i) {
dp[i] = (nums[i - 1] == '0') ? 0 :dp[i - 1];
if (i > 1 && (nums[i - 2] == '1' || (nums[i - 2] == '2' && nums[i - 1] <= '6'))) {
dp[i] += dp[i - 2];
}
}
return dp.back();
}
};
发表于 2020-10-19 16:35:39
回复(0)
class Solution: def solve(self , nums: str) -> int: # write code here n = len(nums) dp = [0] * (n+1) dp[0] = 1 dp[1] = 1 if nums[0] != '0' else 0 print(dp) for i in range(2, n+1): if nums[i-1] != '0': dp[i] += dp[i-1] if '10'<= nums[i-2:i] <= '26': dp[i] += dp[i-2] return dp[n]
发表于 2023-04-10 17:36:45
回复(0)
class Solution: def solve(self , nums: str) -> int: # write code here if not nums&nbs***bsp;nums== '0': return 0 a = b = 1 # a f(i-2) b f(i-1) for i in range(1,len(nums)): tmp = nums[i-1:i+1] if tmp == '00': # 如果有00连续则无法翻译 返回0 return 0 # 有0的如 10 20看成可翻译的一个数，而不是两个数的情况 # c = a + b if '11' <= tmp <= '26' and '0' not in tmp else b c = a + b if '11' <= tmp <= '26' and tmp != '20' else b a, b = b, c return b有条件的青蛙跳， 不仅是11 到 26 还要对0进行处理
发表于 2021-12-17 11:02:45
回复(2)
/**
* 解码
* @param nums string字符串 数字串
* @return int整型
*/
function solve(nums) {
let dp = new Array(nums.length + 1);
dp[0] = 1;
for (let i = 1; i <= nums.length; i++) {
dp[i] = nums[i - 1] == '0' ? 0 : dp[i - 1];
if ((i > 1) && ((nums[i - 2] == '1') || (nums[i - 2] == '2' && nums[i - 1] <= '6'))) {
dp[i] += dp[i - 2];
}
}
return dp[nums.length];
}
module.exports = {
solve: solve
};
发表于 2021-11-21 18:45:46
回复(0)
public int solve (String nums) {
if(nums.equals("")) return 0;
int n=nums.length();
int[]dp=new int[n+1];//dp[i]表示长度为0时译码数
dp[0]=1;
dp[1]=nums.charAt(0)=='0'?0:1;//一位数只要不是0就是一种译码
for(int i=2;i<=n;i++){
int preTwo=Integer.parseInt(nums.substring(i-2,i));//计算自己和前一位是否能组成译码，前i-2和（i-1,i）形成一种译码情况
if(preTwo>=10&&preTwo<=26){
dp[i]=dp[i-2];
}
//检查这一位能否单独译码（这时候的情况是前i-1个和i形成译码）
if(nums.charAt(i-1)!='0') dp[i]+=dp[i-1];
}
return dp[n];
}
发表于 2021-03-26 20:42:15
回复(2)
public int solve (String nums) {
// write code here
int n = nums.length();
int[] dp = new int[n + 1]; // 定义：以nums[i - 1]结尾的字符串的译码次数
dp[0] = 1; // 初始为1(对于dp[2]有用)
dp[1] = nums.charAt(0) == '0' ? 0 : 1;
for(int i = 2; i <= n; i++) {
// 两种译码情况，要么当前数字单独译码，要么与前一位数字结合译码
// 情况1：单独译码（条件是当前数字不是0才行）
if(nums.charAt(i - 1) != '0') {
dp[i] += dp[i - 1];
}
// 情况2：要么与前一位数字结合译码,条件是结合后的数字不超过26
if(nums.charAt(i - 2) == '1' || (nums.charAt(i - 2) == '2' && nums.charAt(i - 1) <= '6')) {
dp[i] += dp[i - 2];
}
}
return dp[n];
}
发表于 2022-05-15 14:11:06
回复(0)
/**
* 解码 这题目本质和矩形覆盖和上楼梯都是一样的 一次编一个一次编两个
* dp[i] 表示前i个字符的编码方式
* 因为0不能被编码所以会有很多特殊情况
* 1.当遍历到0 但前一个字符 不是1或2 无法编译返回0
* 2.当遍历到0 但前一个字符是1 或 2 dp[i] = dp[i-2]
* 3.遍历到的不是0 但和前一个组成的二位数范围不在可解码范围内 dp[i] = dp[i-1]
* 4 其他 dp[i] = dp[i-1] + dp[i-2]
*
* @param nums string字符串 数字串
* @return int整型
*/
public int solve (String nums) {
int m = nums.length();
// 因为最后要返回dp[m] 前m个字符的编码方式 m可以看出字符个数
int[] dp = new int[m + 1];
dp[1] = 1; dp[0] = 1;
for(int i = 2; i <= m; i++){
// 如果遇到一个0前面不是1或者不是2直接返回0无法编译
if(nums.charAt( i -1 ) == '0' && (nums.charAt(i - 2) != '1' && nums.charAt(i - 2) != '2' )) return 0;
// 如果是0 前面一个为1
if(nums.charAt( i -1 ) == '0') dp[i] = dp[i - 2];
else {
if((Integer.valueOf(nums.substring(i -2, i)) <= 26 && Integer.valueOf(nums.substring(i -2, i)) > 10)){
dp[i] = dp[i - 1] + dp[i - 2];
}else dp[i] = dp[i - 1];
}
}
return dp[m];
}
发表于 2022-05-03 18:16:21
回复(0)
能过所有测试用例
public class Solution {
public int solve (String nums) {
// nums可能含有0，但0没有对应的字母字符，所以无法译码，返回0；
// 所以如果nums中含有0，则必须和前一个字符组成10(j)或20(t)一起译码才行，否则都无法译码。
for (int i = 0; i < nums.length(); i++) {
if (nums.charAt(i) == '0') {
if (i - 1 < 0) return 0; // 考虑nums为"0"或"05"此类形式
String temp = nums.substring(i - 1, i + 1); // 获取0和前面一个字符的组合
if ("10".equals(temp) || "20".equals(temp)) continue; // 0能够译码
return 0; // 如果0和前面的一个字符无法组成10或20，则无法译码，返回0
}
}
int[] dp = new int[nums.length() + 1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= nums.length(); i++) {
String temp = nums.substring(i - 2, i);
if ("10".equals(temp) || "20".equals(temp)) {
dp[i] = dp[i - 2]; // 10和20只能组合在一起译码，且只有一种译码结果
} else if (temp.compareTo("10") > 0 && temp.compareTo("26") <= 0) {
dp[i] = dp[i - 1] + dp[i - 2];
} else {
dp[i] = dp[i - 1];
}
}
return dp[nums.length()];
}
}
发表于 2021-09-11 18:34:16
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-02-19 08:55:07
-
2022-09-16 16:19:11
-
2022-09-16 15:25:43
-
2022-09-16 14:17:11 -
2022-09-16 13:37:18
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
