91. Decoding method
Answer:
Notes for creating dp arrays:
- 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;
. - And any position
dp[i]
At most, it has to do with the first two positions. - Therefore create
s.length + 1
The length of thedp
Array 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. - Dp [I] corresponds to the string position s[i-1].
The problem can be broken down into the following scenarios
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];
.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];
.- If you’re judging
10
and20
If, afters[i - 1]
There is a0
, must be present at the moment30
,40
,50
And 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