Решение проблем | «Ликоу» № 639: Метод расшифровки II (сложный)

алгоритм

Решение проблем | «Ликоу» № 639: Метод расшифровки II (сложный)

Аннотация: этот вопрос на самом деле такой же, как 90-й вопрос (метод декодирования I) «Ликоу», за исключением того, что в нем больше подстановочных знаков.*Это усложняет обсуждение классификации.

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

Код ссылки:

public class Solution {

    private int M = 1000000007;

    public int numDecodings(String s) {
        int len = s.length();
        long[] dp = new long[len + 1];
        dp[0] = 1;

        char[] charArray = s.toCharArray();
        if (charArray[0] == '0') {
            return 0;
        }

        if (charArray[0] == '*') {
            dp[1] = 9;
        } else {
            dp[1] = 1;
        }

        for (int i = 2; i <= len; i++) {
            char pre = charArray[i - 2];
            char cur = charArray[i - 1];
            // 情况 1：cur 单独编码，不考虑之前
            if (cur == '*') {
                dp[i] += 9 * dp[i - 1];
            } else if (cur > '0') {
                dp[i] += dp[i - 1];
            }

            // 情况 2：考虑 pre 可以和 cur 合并在一起编码的情况
            if (pre == '*') {
                if (cur == '*') {
                    // 两个 ** 可以有 15 种情况
                    dp[i] += 15 * dp[i - 2];
                } else if (cur <= '6') {
                    // *0、*1、*2、*3、*4、*5、*6 可以拼成
                    // 10、11、12、13、14、15、16
                    // 20、21、22、23、24、25、26 所以这里系数是 2
                    dp[i] += 2 * dp[i - 2];
                } else {
                    // *7 *8 *9 只能拼凑成 1 种情况，就是 17、18、19
                    dp[i] += dp[i - 2];
                }
            } else if (pre == '1' || pre == '2') {
                if (cur == '*') {
                    // 1*、2* 的时候
                    // 特别注意：10 和 20 的情况上面已经讨论过了，所以不可以重复加上去
                    if (pre == '1') {
                        // 1* 可以拼成 11、12、13、14、15、16、17、18、19
                        dp[i] += 9 * dp[i - 2];
                    } else {
                        // 2* 可以拼成 21、22、23、24、25、26
                        dp[i] += 6 * dp[i - 2];
                    }
                } else if (((pre - '0') * 10 + (cur - '0')) <= 26) {
                    // 当 pre 和 cur 并非通配符，且两个字符可以拼成一个的情况
                    dp[i] += dp[i - 2];
                }
            }
            dp[i] %= M;
        }
        return (int) dp[len];
    }
}
Категории