image.png
image.png

传送门：https://leetcode-cn.com/problems/decode-ways/

题目

一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：

‘A’ -> 1 ‘B’ -> 2 … ‘Z’ -> 26

解码已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。 例如，”111” 可以将 “1” 中的每个 “1” 映射为 “A” ，从而得到 “AAA” ，或者可以将 “11” 和 “1” （分别为 “K” 和 “A” ）映射为 “KA” 。注意，”06” 不能映射为 “F” ，因为 “6” 和 “06” 不同。

给你一个只含数字的 非空 字符串 num ，请计算并返回 解码 方法的 总数 。

示例 1：

输入：s = “12” 输出：2 解释：它可以解码为 “AB”（1 2）或者 “L”（12）。


示例 2：**

输入：s = “226” 输出：3 解释：它可以解码为 “BZ” (2 26), “VF” (22 6), 或者 “BBF” (2 2 6) 。


示例 3：**

输入：s = “0” 输出：0 解释：没有字符映射到以 0 开头的数字。含有 0 的有效映射是 ‘J’ -> “10” 和 ‘T’-> “20” 。由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。


示例 4：**

输入：s = “06” 输出：0 解释：”06” 不能映射到 “F” ，因为字符串开头的 0 无法指向一个有效的字符。

解题思路：动态规划->滚动数组

设 dp[i] 为 str[0...i] 的解码方式的总个数。
若str[i] 能够与 str[i-1] 合并解码 u(i,i-1)=1
若str[i] 不能与 str[i-1] 合并解码 u(i,i-1)=0

我们不难发现，dp[i] 的值在于 str[i] 能否与 str[i-1] 合并解码。

  1.   - `u(i,i-1)=1`，`dp[i]=dp[i-2]+dp[i-1]`
  2.   - `u(i,i-1)=0`，`dp[i]=dp[i-1]`

状态转移方程：

🚩[LeetCode]Dp91 解码方法 [动态规划->滚动数组] - 图3**

边界条件和特殊 🚩[LeetCode]Dp91 解码方法 [动态规划->滚动数组] - 图4 特殊处理

复杂度分析

时间复杂度：🚩[LeetCode]Dp91 解码方法 [动态规划->滚动数组] - 图5，其中 🚩[LeetCode]Dp91 解码方法 [动态规划->滚动数组] - 图6 为 🚩[LeetCode]Dp91 解码方法 [动态规划->滚动数组] - 图7 数组长度。

空间复杂度：🚩[LeetCode]Dp91 解码方法 [动态规划->滚动数组] - 图8，其中 🚩[LeetCode]Dp91 解码方法 [动态规划->滚动数组] - 图9 为 🚩[LeetCode]Dp91 解码方法 [动态规划->滚动数组] - 图10 数组长度。
利用滚动数组优化，我们可以从 🚩[LeetCode]Dp91 解码方法 [动态规划->滚动数组] - 图11 优化到 🚩[LeetCode]Dp91 解码方法 [动态规划->滚动数组] - 图12 。

代码

我的代码 [ 动态规划 ] 😱羞愧

  1. public class Demo {
  2.     //动态规划:dp[i]代表[0....i]所能解析出的编码总数
  3.     //状态转移方程:dp[i]=dp[i-1]+dp[i-2](能结合的情况下)
  4.     public static int numDecodings(String s) {
  5.         if(s==null||s.length()==0)return 0;
  6.         if(s.charAt(0)=='0')return 0;
  7.         if(s.length()==1)return 1;
  8.         int[]dp=new int[s.length()];
  9.         //进来的一定是合法串,且开头不为0,个数大于等于2
  10.         dp[0]=1;
  11.         //状态转移
  12.         for (int i = 1; i < s.length(); i++) {
  13.             if(s.charAt(i)-'0'==0) {//遇到编码为0说明无法解码,看能否和前面的数字结合
  14.                 if(i==1){//开始第2个数就是0
  15.                     if(Integer.valueOf(s.charAt(i-1)+""+s.charAt(i))<=26) dp[i]=1;
  16.                     //当不能前后结合dp[i]=0,由于dp默认初始就是0,故不用操作
  17.                 }else{//出现的0小标大于1
  18.                     if(Integer.valueOf(s.charAt(i-1)+""+s.charAt(i))<=26)dp[i]=dp[i-2];
  19.                     //当不能前后结合dp[i]=0,由于dp默认初始就是0,故不用操作
  20.                 }
  21.                 if(i+1<s.length()){
  22.                     if(s.charAt(i+1)-'0'==0)return 0;//连续两个0不可能解码成功
  23.                     dp[i+1]=dp[i];i++;
  24.                 }
  25.                 continue;
  26.             }
  27.             if(i==1){//处理2个数字
  28.                 if(Integer.valueOf(s.charAt(i-1)+""+s.charAt(i))<=26)dp[i]=2;
  29.                 else dp[i]= 1;
  30.             }else{
  31.                 //此时个数大于2以上的,最后两个数字能结合解码
  32.                 if(Integer.valueOf(s.charAt(i-1)+""+s.charAt(i))<=26){
  33.                     dp[i]=dp[i-1]+dp[i-2];
  34.                 }else
  35.                     dp[i]=dp[i-1];
  36.             }
  37.         }
  38.         return dp[s.length()-1];
  39.     }
  41.     public static void main(String[] args) {
  42.         System.out.println(numDecodings("1201234"));
  43.     }
  44. }

官方代码

public class Demo {
     static int numDecodings(String s) {
        if (s.charAt(0) == '0') return 0;
        int pre = 1, curr = 1;//dp[-1] = dp[0] = 1
        for (int i = 1; i < s.length(); i++) {
            int tmp = curr;
            if (s.charAt(i) == '0')
                if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2') curr = pre;
                else return 0;
            else if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' 
                        && s.charAt(i) >= '1' && s.charAt(i)  <= '6'))
                curr = curr + pre;
            pre = tmp;
        }
        return curr;
    }

    public static void main(String[] args) {
        System.out.println(numDecodings("1201234"));
    }
}

思路解释：
**
设 dp[i] 为 str[0...i] 的解码方式的总个数。
分情况讨论建立最优子结构：

  - 若 `str[i] ='0'` ，当 `s[i-1]='1'or'2'` 时，则 `dp[i]=dp[i-2]`；否则 `return 0`
     - 解释：`s[i-1]+s[i]` 必须合并起来解码
  - 若 `str[i]!='0'` ，当 `str[i-1]='1'` 时，则`dp[i]=dp[i-1]+dp[i-2]`
     - 解释：`s[i-1]` 与 `s[i]` 分开解码为 `dp[i-1]`，合并解码为 `dp[i-2]`
  - 若 `str[i]!='0'` ，当 `str[i-1]='2'and'1'<=str[i]<='6'` 时，则 `dp[i]=dp[i-1]+dp[i-2]`
     - 解释：同上

由分析可知，dp[i] 仅与dp[i-1] 、dp[i-2]有关，故可以用滚动数组代替，将空间复杂度降至 🚩[LeetCode]Dp91 解码方法 [动态规划->滚动数组] - 图13

🦄我的代码 [ 滚动数组 ]

public class Demo {
    static int numDecodings(String s) {
        if(s==null||s.length()==0)return 0;
        if (s.charAt(0) == '0') return 0;
        int dpi=1,dpi_1=1,dpi_2=1;    //dp[i-1]=dpi_1
        for (int i = 1; i < s.length(); i++) {    //状态转移
            if(s.charAt(i)=='0'){                //s[i]为0,0的前面必须要是1,2才能结合解码
                if(s.charAt(i-1)=='1'||s.charAt(i-1)=='2') dpi=dpi_2;
                else return 0;
            }else if((s.charAt(i-1)=='1')||s.charAt(i-1)=='2'
                     &&(s.charAt(i)>='0'&&s.charAt(i)<='6')){    //s[i]非0,但和前面可以结合解码
                dpi=dpi_1+dpi_2;
            }else dpi=dpi_1;    //s[i]非0,但和前面不能结合
            dpi_2=dpi_1;//数组滚动
            dpi_1=dpi;
        }
        return dpi;
    }
    public static void main(String[] args) {
        System.out.println(numDecodings("1201234"));
    }
}