This is the 13th day of my participation in the First Challenge 2022

Recommended reading

  • CSDN home page
  • GitHub open source address
  • Unity3D plugin sharing
  • Jane’s address book
  • My personal blog
  • QQ group: 1040082875

Hello, everyone, I am a little Magic dragon, Unity3D software engineer, VR, AR, virtual simulation direction, update software development skills from time to time, life perception, remember to use one button three links.

A, the title

1. Algorithm topic

“Given a numeric string, compute and return the sum of the decoding methods.”

Title link:

Source: LeetCode

Link: 91. Decoding method – LeetCode (leetcode-cn.com)

2

A message containing the letters A-Z is encoded by the following mapping:

‘A’ -> “1” ‘B’ -> “2” … ‘Z’ -> “26”

To decode the encoded message, all numbers must be mapped back to letters, based on the above method of mapping (there may be several methods). For example, “11106” can be mapped to:

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

Note that messages cannot be grouped as (1 11 06) because “06” cannot be mapped to “F”, since “6” and “06” are not equivalent in the mapping.

Given a non-empty string s containing only numbers, count and return the total number of decoding methods.

The data guarantees that the answer is a 32 – digit integer.

Example 1: Input: s = "12" Output: 2 Explanation: It can be decoded as either "AB" (1, 2) or "L" (12).Copy the code
Example 2: Input: s = "226" Output: 3 Explanation: It can be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 26).Copy the code

Second, the problem solving

1. Analysis of ideas

This problem dynamic programming, recursion can be.

Parse the problem first, decode the given string s, and return the number of decodes.

Specifically, for the string S, two situations will occur when determining which characters in S are used in the decoding:

  • A character is used to decode s[I], which can be decoded into A letter in A~I, and then the remaining characters are decoded
  • Two characters, s[I] and s[i-1], are used to decode. Similar to the first case, s[i-1] cannot equal 0, and the integer s[i-1] and S [I] must be less than or equal to 26

Thus, state transition mode can be written to carry out dynamic planning:

Fi = fi – 1, s [I] / fi = 0 fi – 2, the s/I – 1 indicates a 0, and 10 * s + s [I – 1] [I] 26 or less

2. Code implementation

Code reference:

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;
        }
        returnc; }}Copy the code

3. Time complexity

Time complexity: O(n)

Where n is the length of the string s.

Space complexity: O(n)

The space complexity is O(n) if an array is used for state transitions, and O(1) if only three variables are used.

Third, summary

This problem first needs to understand the decoding rules clearly.

Find the dynamic programming equation and use dynamic programming to find the answer.