当前位置:网站首页>Leetcode 91. Decoding method

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[1],s[2],⋯,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 fi 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 :

 Insert picture description here

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 fi Value . After the dynamic planning is completed , The final answer is f n f_n fn .

details

The boundary condition of dynamic programming is f 0 = 1 f_0 = 1 f0=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[0] = 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 fi The value of is only associated with f i − 1 f_{i-1} fi1​ and f i − 2 f_{i-2} fi2 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 = [1] + [0] * 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).

版权声明
本文为[ZSYL]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/08/20210808001155879M.html

随机推荐