P88 解码方式

描述#

这个题目说的是，给你一个加密后的非空字符串，原字符串由大写 A 到 Z 组成，加密后的字符串由数字字符组成，加密方法是把大写 A 到 Z 映射成 1 到 26。你要计算出给你的加密字符串有多少种可能的解码方式。

比如说，给你的加密字符串是："124"。这个数字字符串有 3 种解码方式：

第一种是 "124" 各解码成一个字符，得到 ABD
第二种是 "12" 和 "4" 各解码成一个字符，得到 LD
第三种是 "1" 和 "24" 各解码成一个字符，得到 AX

因此，你要返回的答案就是 3 种。
映射关系：
A -> 1
B -> 2
...
Z -> 26

代码#

public class AlgoCasts {

  private boolean isValidTwoDigit(char a, char b) {
    return (a == '1' && b <= '9') || (a == '2' && b <= '6');
  }

  private int decode(char[] c, int i) {
    if (i == c.length) return 1;
    if (i > c.length) return 0;
    int num = 0;
    if (c[i] != '0') num += decode(c, i+1);
    if (i+1 < c.length && isValidTwoDigit(c[i], c[i+1])) num += decode(c, i+2);
    return num;
  }

  public int numberOfDecodingsRecursive(String s) {
    return decode(s.toCharArray(), 0);
  }

  // Time: O(n), Space: O(n)
  public int numberOfDecodingsDP(String s) {
    int[] d = new int[s.length() + 1];
    d[0] = 1;
    d[1] = s.charAt(0) != '0' ? 1 : 0;
    for (int i = 2; i <= s.length(); ++i) {
      if (s.charAt(i-1) != '0') d[i] += d[i-1];
      if (isValidTwoDigit(s.charAt(i-2), s.charAt(i-1))) d[i] += d[i-2];
    }
    return d[s.length()];
  }

  // Time: O(n), Space: O(1)
  public int numberOfDecodingsDPO1(String s) {
    int first = 1;
    int second = s.charAt(0) != '0' ? 1 : 0;
    for (int i = 2; i <= s.length(); ++i) {
      int third = 0;
      if (s.charAt(i-1) != '0') third += second;
      if (isValidTwoDigit(s.charAt(i-2), s.charAt(i-1))) third += first;
      first = second;
      second = third;
    }
    return second;
  }

}