91. 解码方法

题目描述

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

'A' -> 1
'B' -> 2
...
'Z' -> 26

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1 1 10 6)
• "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 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) 。

示例 3：

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

示例 4：

输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。

方法：动态规划

对于给定的字符串 $s$，设它的长度为 $n$，其中的字符从左到右依次为 $s[1], s[2], \cdots, s[n]$。我们可以使用动态规划的方法计算出字符串 $s$ 的解码方法数。

具体地，设 $f_i$ 表示字符串 $s$ 的前 $i$ 个字符 $s[1..i]$ 的解码方法数。在进行状态转移时，我们可以考虑最后一次解码使用了 $s$ 中的哪些字符，那么会有下面的两种情况：

• 第一种情况是我们使用了一个字符，即 $s[i]$ 进行解码，那么只要 $s[i] \neq 0$，它就可以被解码成 $\text{A} \sim \text{I}$ 中的某个字母。由于剩余的前 $i−1$ 个字符的解码方法数为 $f_{i-1}$ ，因此我们可以写出状态转移方程： \(f_i=f{i−1},其中 s[i]=0\)

• 第二种情况是我们使用了两个字符，即 $s[i-1]$ 和 $s[i]$ 进行编码。与第一种情况类似，$s[i-1]$ 不能等于 $0$，并且 $s[i−1]$ 和 $s[i]$ 组成的整数必须小于等于 $26$，这样它们就可以被解码成 $\text{J} \sim \text{Z}$ 中的某个字母。由于剩余的前 $i−2$ 个字符的解码方法数为 $f_{i-2}$，因此我们可以写出状态转移方程： \(f_i=f_{i−2},其中 s[i−1]=0 且 10⋅s[i−1]+s[i]≤26\)

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

  优化：

  class Solution {
      public int numDecodings(String s) {
          int n = s.length();
          // a = f[i-2], b = f[i-1], c=f[i]
          int a = 0, b = 1, c = 0;
          for (int i = 1; i <= n; ++i) {
              c = 0;
              if (s.charAt(i - 1) != '0') {
                  c += b;
              }
              if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {
                  c += a;
              }
              a = b;
              b = c;
          }
          return c;
      }
  }
  

  哈希表代替

  class Solution {
      public int numDecodings(String s) {
      HashMap<Integer, Integer> memoization = new HashMap<>();
      return getAns(s, 0, memoization);
  }
    
  private int getAns(String s, int start, HashMap<Integer, Integer> memoization) {
      if (start == s.length()) {
          return 1;
      }
      if (s.charAt(start) == '0') {
          return 0;
      }
      //判断之前是否计算过
      int m = memoization.getOrDefault(start, -1);
      if (m != -1) {
          return m;
      }
      int ans1 = getAns(s, start + 1, memoization);
      int ans2 = 0;
      if (start < s.length() - 1) {
          int ten = (s.charAt(start) - '0') * 10;
          int one = s.charAt(start + 1) - '0';
          if (ten + one <= 26) {
              ans2 = getAns(s, start + 2, memoization);
          }
      }
      //将结果保存
      memoization.put(start, ans1 + ans2);
      return ans1 + ans2;
      }
  }