The decoding method

Title Description: 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 method of mapping described above (there may be several methods). For example, “11106” can be mapped to:

“AAJF”, groups the messages into (11 10 6) “KJF”, groups the messages into (11 10 6) note that the messages cannot be grouped into (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.

Examples can be found on the LeetCode website.

Source: LeetCode link: leetcode-cn.com/problems/de… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Solution 1: recursive exhaustion
  • First of all, when s is null or an empty string or s starts with 0, the mapping is not possible and 0 is returned.
  • If s has length 1, return 1.
  • And then we recursively handle whensIf the length is greater than 1, the recursive method handles the logic as follows (method input argumentsleftandrightAre the start and end positions of the current character to be matched0 < (right - left) < 3) :
    • If the number in the left position is 0, that is, the character to be matched starts with 0, the mapping cannot be performed.
    • If the number of characters matched by left and right is greater than 26, the mapping cannot be performed.
    • If right is the last digit of s, result increments by 1;
    • If right is the penultimate digit of s and the last digit is not 0, result increments by 1;
    • Then we continue recursive processing based on the number of digits after rightright ~ right + 1andright ~ right + 2In the case.
  • Result is the total number of decoding methods.
public class LeetCode_091 {

    private static int result = 0;

    /** * Recursive exhaustion: poor performance, lift timeout **@param s
     * @return* /
    public static int numDecodings(String s) {
        // These cases cannot be mapped and return 0
        if (s == null || s == "" || s.equals("0") || s.startsWith("0")) {
            return 0;
        }

        if (s.length() == 1) {
            return 1;
        }

        numDecodings(s, 0.1);
        numDecodings(s, 0.2);
        return result;
    }



    public static void numDecodings(String s, int left, int right) {
        if (s.charAt(left) == '0') {
            return;
        }
        if (Integer.valueOf(s.substring(left, right)) > 26) {
            return;
        }
        if (s.length() - right == 0) {
            result++;
            return;
        }
        if (s.length() - right == 1 && s.charAt(s.length() - 1) != '0') {
            result++;
            return;
        }
        numDecodings(s, right, right + 1);
        if (s.length() - right > 1) {
            numDecodings(s, right, right + 2); }}public static void main(String[] args) {
        System.out.println(numDecodings("226")); }}Copy the code

【 Daily Message 】 Struggle with heaven, great fun! With the struggle, fun! Struggle with people, fun!