91. Decoding method

Answer:

Notes for creating dp arrays:

  1. According to the passage,s[0]May be'0'or'1'And we can derive it very simplys[0]The initial state of is:dp[1] = s[0] === '0' ? 0:1;.
  2. And any positiondp[i]At most, it has to do with the first two positions.
  3. Therefore creates.length + 1The length of thedpArray and initializedp[0] = 1, to ensure that you can look up the state of two digits forward, which is virtual by defaults[-1]The location is the code of compliance.
  4. Dp [I] corresponds to the string position s[i-1].

The problem can be broken down into the following scenarios

  1. s[i - 1]The coding range of is1-9, no new encoding method will be generated, and the state transition equation is:dp[i] = dp[i - 1];.
  2. s[i - 2] + s[i - 1]The range is10 ~ 26.dp[i]withdp[i - 1]anddp[i - 2]To do withdp[i - 1]The state transition equation for this condition has been calculated in Step 1:dp[i] += dp[i - 2];.
  3. If you’re judging10and20If, afters[i - 1]There is a0, must be present at the moment30,40,50And so cannot decode the case, can directly return 0.
/ * * *@param {string} s
 * @return {number}* /
var numDecodings = function (s) {
  // Create a recursive array of s.length + 1, indexed from 1 to s.length, for each position of s
  // dp[I] corresponds to the string position s[i-1].
  let dp = new Array(s.length + 1).fill(0);
  // Since the state of dp[I] is related to dp[i-1] and dp[i-2], we can only create the initial state of s[0]
  // Set position 0 to 1 to ensure efficient recursion.
  dp[0] = 1;
  // Create the initial state of s[0], where the decoding method is 0
  dp[1] = s[0= = ='0' ? 0 : 1;

  // Start from s[1]
  for (let i = 2; i < dp.length; i++) {
    let one = s[i - 1]; // The encoding of the current location
    let two = s[i - 2] + s[i - 1]; // A sequence of two digits

    // If the current position code is 0-9, no new method is added, and the number of methods is the same as dp[i-1]
    if (one >= '1' && one <= '9') {
      dp[i] = dp[i - 1];
    }
    Dp [i-2] = dp[i-2] = dp[i-2]
    // Dp [i-1] is already accumulated
    if (two >= '10' && two <= '26') {
      dp[i] += dp[i - 2];
    } else if (one === '0') {
      // The current encoding is 0, cannot decode, return 0
      // The encoding for 10 and 20 has already been handled and these scenarios are not included here
      return 0; }}// The number of decoding methods is found
  return dp[s.length];
};
Copy the code