# Leetcode 91. Decoding method

2021-08-08 00:13:33 ZSYL

# Title Description

One contains letters A-Z The message is mapped as follows code ：

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


want decode Encoded message , All numbers must be based on the above mapping method , Back to letters （ There may be several ways ）. for example ,“11106” It can be mapped to ：

• “AAJF” , Group messages into (1 1 10 6)
• “KJF” , Group messages into (11 10 6)

Be careful , Messages cannot be grouped into (1 11 06) , because “06” Cannot map to “F” , This is because “6” and “06” It's not equivalent in mapping .

Here's a number only Non empty character string s , Please calculate and return decode Methodical total .

The question data guarantee that the answer is definitely one 32 position The integer of .

Example :

 Input ：s = "12"
Output ：2
explain ： It can be decoded as  "AB"（1 2） perhaps  "L"（12）.


# Dynamic programming

For a given string s, Let its length be n, The characters are... From left to right s,s,⋯,s[n]. We can use the dynamic programming method to calculate the string s Number of decoding methods .

In particular , set up f i f_i Representation string s Before i Characters s[1…i] Number of decoding methods . During state transition , We can consider using... For the last decoding s Which characters in , Then there will be the following two situations ： It should be noted that , Only when i>1 Transfer can only be carried out when , otherwise s[i−1] non-existent .

Put the two above State transition equation Accumulate when the corresponding conditions are met , You can get f i f_i Value . After the dynamic planning is completed , The final answer is f n f_n .

details

The boundary condition of dynamic programming is f 0 = 1 f_0 = 1

That is, an empty string can have 1 A decoding method , Decode an empty string .

# Reference code

## Java

class Solution {

public int numDecodings(String s) {

int n = s.length();
int[] dp = new int[n + 1];
dp = 1;
for (int i = 1; i <= n; ++i) {

if (s.charAt(i - 1) != '0') {

dp[i] += dp[i - 1];
}
if (i > 1 && s.charAt(i - 2) != '0' && ((s.charAt(i - 2) - '0') * 10 + (s.charAt(i - 1) - '0') <= 26)) {

dp[i] += dp[i - 2];
}
}
return dp[n];
}
}


Note that in the state transition equation , f i f_i The value of is only associated with f i − 1 f_{i-1} ​ and f i − 2 f_{i-2} of , So we can use three variables for state transition , Save the space of the array .

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;
}
}


## Python

class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
dp =  +  * n
for i in range(1, n + 1):
if s[i - 1] != '0':
dp[i] += dp[i - 1]
if i > 1 and s[i - 2] != '0' and int(s[i-2:i]) <= 26:
dp[i] += dp[i - 2]
return dp[n]

class Solution:
def numDecodings(self, s: str) -> int:
n = len(s)
# a = f[i-2], b = f[i-1], c = f[i]
a, b, c = 0, 1, 0
for i in range(1, n + 1):
c = 0
if s[i - 1] != '0':
c += b
if i > 1 and s[i - 2] != '0' and int(s[i-2:i]) <= 26:
c += a
a, b = b, c
return c


Complexity analysis

• Time complexity ：O(n), among nn Is string ss The length of .
• Spatial complexity ：O(n) or O(1). If you use an array for state transition , The space complexity is O(n); If only three variables are used , The space complexity is O(1).

https://chowdera.com/2021/08/20210808001155879M.html