[Leetcode][Medium] Способы декодирования Методы декодирования | Java

вопрос

Decode Ways Medium

A message containing letters from A-Z can be encoded into numbers using the following mapping:

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

To decode an encoded message, all the digits must be grouped then mapped back into letters using the reverse of the mapping above (there may be multiple ways). For example, "11106" can be mapped into:

• "AAJF" with the grouping (1 1 10 6)
• "KJF" with the grouping (11 10 6)

Note that the grouping (1 11 06) is invalid because "06" cannot be mapped into 'F' since "6" is different from "06".

Given a string s containing only digits, return the number of ways to decode it.

The answer is guaranteed to fit in a 32-bit integer.

 

Example 1:

Input: s = "12"
Output: 2
Explanation: "12" could be decoded as "AB" (1 2) or "L" (12).

Example 2:

Input: s = "226"
Output: 3
Explanation: "226" could be decoded as "BZ" (2 26), "VF" (22 6), or "BBF" (2 2 6).

Example 3:

Input: s = "0"
Output: 0
Explanation: There is no character that is mapped to a number starting with 0.
The only valid mappings with 0 are 'J' -> "10" and 'T' -> "20", neither of which start with 0.
Hence, there are no valid ways to decode this since all digits need to be mapped.

Example 4:

Input: s = "06"
Output: 0
Explanation: "06" cannot be mapped to "F" because of the leading zero ("6" is different from "06").

 

Constraints:

• 1 <= s.length <= 100
• s contains only digits and may contain leading zero(s).

Идеи решения проблем

Этот вопрос требует вычислить, сколько возможных методов декодирования доступно Это типичная задача оптимальной подструктуры, которую можно использоватьдинамическое программированиеполучить оптимальное решение.

мы определяем$dp(i)$как строкаsподстрока вs(0,i)количество методов декодирования. Тогда окончательное решение этой задачи$dp(n-1)$,nкак строкаsдлина. Далее необходимо сделать выводуравнение перехода состояния,Например$dp(i+1)=dp(i)+1$, разбить сложную проблему на подзадачи и решить их рекурсивно.

Сначала разберем специальную кодировку0. первый0Буква не может быть представлена ​​сама по себе, еслиsПервая кодировка0, его нельзя расшифровать. Второй0только с предыдущим1или2объединены для обозначения буквы, есть только одна возможность, поэтому, еслиs[i] == 0а такжеs[i-1] in (1,2),Так$dp(i)=dp(i-2)$.

когдаs[i]не для0когда (при условии, что кодировкаy), он может быть совместим с предыдущей кодировкойxкомбинация, в настоящее время может быть два метода декодирования, иxв сочетании сxy, либо не объединены, а представлены по отдельности в видеx,y.

1. Когда комбинация возможна, например, x=1, y=3, тогда$дп (я) = дп (я-2) + дп (я-1)$

• Если объединить вxy,но$дп(я) = дп(я-2)$
• Если он стоит один, какy,но$дп (я) = дп (я-1)$

2. Когда комбинации невозможны, например, x=2, y=9,yв настоящее время может представлять только одну букву$дп (я) = дп (я-1)$

Отсюда мы можем получить следующий код.

справочный ответ

public class Solution {

    public int numDecodings(String s) {
        int n = s.length();
        int[] dp = new int[n];
        if (s.charAt(0) == '0') {
            return 0;
        }
        dp[0] = 1;

        for (int i = 1; i < n; i++) {
            if (s.charAt(i) == '0') {
                // only 10 and 20 are valid, and it doesn't increase the number of decoding ways 
                if (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2') {
                    dp[i] = i-2 >= 0 ? dp[i-2] : 1;
                
                // 00 or 30... is invalid
                } else {
                    return 0;
                }
            } else if (s.charAt(i - 1) == '1'
                || (s.charAt(i) <= '6' && s.charAt(i - 1) == '2')) {
                // if 11= < xy <= 26 it can be decoded in 2 ways: x,y or xy
                dp[i] = i-2 >= 0 ? dp[i-2] + dp[i-1] : 2;
            } else {
                // if xy < 10 or xy > 26 it can only be decoded in 1 way: x,y
                dp[i] = dp[i-1];
            }
        }

        return dp[n-1];
    }
}

Внешняя граница

Ознакомьтесь с другими задачами динамического программирования!

[Leetcode][Hard] Удаление ящиков | Java

Или зайдите в колонку автора LeetCode, чтобы узнать, есть ли другие интересные вопросы!

Наггетс.Талант/колонка/6997…

Информационная ссылка

• оригинальное название

Ли ТСО's.com/problems/…

• динамическое программирование

This.Wikipedia.org/wiki/%E5%8A…