LeetCode题解：解码方法

题目描述

一个包含字母A-Z的消息通过以下映射进行编码：
'A' ->"1"
'B'->"2"
……
'Z'->"26"
要解码已编码的消息，所有数字必须基于上诉映射的方法，方向映射回字母 （可能有多种方法）例如，“11106”可以映射为：

• "AAJF"，将消息分组为（1 1 10 6）
• "KJF"，将消息分组为（11 10 6）
  注意，消息不能为（11 1 06），因为“06”不能映射为"F"，这是因为“06”和“6”在映射中不等价。
  给你一个只含数字的非空字符串s，请计算并返回解码方法的总数。
  题目数据保证答案肯定是一个32位的整数。

示例

• 示例1
  输入：s = "12"
  输出：2
  解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
• 示例2
  输入：s = "226"
  输出：3
  解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

方法思路

动态规划

class Solution {
    public int numDecodings(String s) {
     int length = s.length();
     int[] array = new int[length+1];
     array[0] = 1;
     for(int i=1;i<length+1;i++){
         if(s.charAt(i-1)!='0'){
             array[i]+=array[i-1];
         }
         if(i>1&&s.charAt(i-2)!='0'&&((s.charAt(i-2)-'0')*10+(s.charAt(i-1)-'0'))<=26){
             array[i]+=array[i-2];
         }
     } 
     return array[length];   
    }
}

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(n)