本文主要是介绍小白教你把数字翻译成字符串,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
把数字翻译成字符串
题目描述:
有一种将字母编码成数字的方式:‘a’->1, ‘b->2’, … , ‘z->26’。
现在给一串数字,返回有多少种可能的译码结果
示例1:
输入:“12”
返回:2
说明:2种可能的译码结果(”ab” 或”l”)
示例2:
输入:“31717126241541717”
返回:192
说明:192种可能的译码结果
题目链接:
把数字翻译成字符串
思路:
小白看到这个问题的时候并不知道如何下手,后来想到了dp,也就是动态规划。我们可不可以一个个增加字符,然后通过前面的组合数,推出以当前字符结束时的组合数。由此我们仔细考虑后会出现以下情况:
代码:
import java.util.*;public class Solution {/*** 解码* @param nums string字符串 数字串* @return int整型*/public int solve (String nums) {// write code hereif(nums.charAt(0) == '0') return 0;int [] dp = new int[nums.length()];//dp[i]的含义代表长度在i位置时有几种翻译办法dp[0] = 1;//在第0个字符的时候只有一个字母所以只有一种翻译办法for(int i = 1;i < nums.length();i ++){if(nums.charAt(i) == '0'){if(nums.charAt(i-1) == '1' || nums.charAt(i-1) == '2'){if(i == 1) dp[i] = 1;//特判字符串长度为2else dp[i] = dp[i-2];//因为 10 20 这样的只有一种对应方案,所以此时dp[i]取决于dp[i-2]}}else if(nums.charAt(i-1) == '1' || (nums.charAt(i-1) == '2' && nums.charAt(i) >= '1' && nums.charAt(i) <= '6')){/*11-26 抛去 20这样的组合但是当i==1的时候如 12 21 这样有两种方案当i>1时候dp[i] 取决于 dp[i-1] 和 dp[i-2]的和*/if(i == 1) dp[i] = 2;else dp[i] = dp[i-1] + dp[i-2];}else{//>=27这样的组合dp[i] = dp[i-1];} }return dp[nums.length() - 1];}
}
这篇关于小白教你把数字翻译成字符串的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!