解码方法

[louzhedong]

习题

出处：LeetCode 算法第91题

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

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

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

思路

本题涉及到字符串的问题，并且是求可能性的总数量，首先想到的就是递归，但当字符串很长的情况下，会超出时间限制。

仔细观察逻辑，发现长度为s的字符串的可能性可以由长度s-1和s-1的可能性得到。所以我们可以采用动态规划

解答

方法1：递归

/**
 * @param {string} s
 * @return {number}
 */
var numDecodings = function (s) {
  var result = [];
  var temp = [];
  helper(result, temp, s);
  return result.length;
};

function helper(result, temp, str) {
  if (!str) {
    result.push(temp);
    return;
  }
  if (str.length >= 2 && Number(str.substr(0, 2)) <= 26 && Number(str.substr(0, 2)) > 0 && !str.startsWith('0')) {
    temp.push(str.substr(0, 2));
    helper(result, temp, str.substr(2));
    temp.pop();
  }
  if (str.length >= 1 && Number(str.substr(0, 1)) > 0) {
    temp.push(str.substr(0, 1));
    helper(result, temp, str.substr(1));
    temp.pop();
  }
}

方法2：动态规划

var numDecodings = function (s) {
  if (s.length === 0) {
    return 0;
  }
  if (s.length === 1) {
    if (s[0] !== '0') {
      return 1;
    } else {
      return 0;
    }
  }
  var length = s.length;
  var dp = [];
  dp[0] = 1;
  if (s[0] !== '0') {
    dp[1] = 1;
  } else {
    dp[1] = 0;
  }

  for (var i = 2; i <= length; i++) {
    var flag1 = ((Number(s.substr(i - 2, 2)) > 0 && Number(s.substr(i - 2, 2)) <= 26 && !s.substr(i - 2, 2).startsWith('0')) ? 1 : 0);
    var flag2 = (s[i - 1] == '0' ? 0 : 1)
    dp[i] = dp[i - 2] * flag1 + dp[i - 1] * flag2;
  }
  return dp[length];
}