JZ46 把数字翻译成字符串

描述

有一种将字母编码成数字的方式：a->1, b->2, ... , z->26             。 现在给一串数字  
  
  
  
  
  
 ，返回有多少种可能的译码结果 示例1 输入： "12" 返回值：2 说明： 2种可能的译码结果（             ”ab 
 
  
 
  
 
  
 
  
 
  
 
  
” 或











”l
  
  
  
  
  
  
 ”）

思路

思路： 对于普通数组1-9 
  
  
  
  
  
  ，译码方式只有一种


 


 


 


 


 


 

，但是对于11-19 
 
 
 
 
 
，21-26  
   
   
   
   
   
   ，译码方式有可选择的两种方案

 

 

 

 

 

 
，因此我们使用动态规划将两种方案累计 
 
  
 
  
 
  
 
  
 
  
 
  
。 具体做法： step 1：用辅助数组dp表示前i个数的译码方法有多少种











。 step 2：对于一个数
 

 

 

 

 

 

，我们可以直接译码它             ，也可以将其与前面的1或者2组合起来译码：如果直接译码
 

 
 

 
 

 
 

 
 

 
 

 
 ，则dp[i]=dp[i−1]；如果组合译码












，则dp[i]=dp[i−2]
  
  
  
  
  
  
 。 step 3：对于只有一种译码方式的                   ，选上种dp[i−1]即可
 
 
 
 
 
 
 
 
 
 
 
 
 ，对于满足两种译码方式（10


















，20不能）则是dp[i−1]+dp[i−2] step 4：依次相加             ，最后的dp[length]即为所求答案 
  
  
  
  
  
 。

代码

package mid.JZ46把数字翻译成字符串; import java.util.*; public class Solution { /** * 解码 * * @param nums string字符串 数字串 * @return int整型 */ public int solve(String nums) { // write code here //如果是0
 
  
 
  
 
  
 
  
 
  
 
  
 ，直接排除 if (nums.equals("0")) return 0; //如果是10 或者 20 就一种直接返回 if (nums.equals("10") || nums.equals("20")) return 1; //如果后一位为0前一位不为1或者2 不行 for (int i = 1; i < nums.length(); i++) { if (nums.charAt(i) == 0) { if (nums.charAt(i - 1) != 1 && nums.charAt(i - 1) != 2) return 0; } } int[] dp = new int[nums.length() + 1]; Arrays.fill(dp, 1); for (int i = 2; i <= nums.length(); i++) { if ((nums.charAt(i - 2) == 1 && nums.charAt(i - 1) != 0) || ((nums.charAt(i - 2) == 2 && (nums.charAt((i - 1)) > 0 && nums.charAt(i - 1) < 7)))) dp[i] = dp[i - 1] + dp[i - 2]; else dp[i] = dp[i - 1]; } return dp[nums.length()]; } public static void main(String[] args) { System.out.println(new Solution().solve("12")); } }