[数据结构与算法]LeetCode每日一题(Decode Ways)

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).

这题最好的讲解就是代码, 不过我不保证我的代码是最优雅的，应该有不少地方还可以简化，但是整体的思路应该没问题

代码实现(Rust):

impl Solution {
    pub fn num_decodings(s: String) -> i32 {
        // 如果只有一个字符则判断是不是'0'
        if s.len() == 1 {
            if s == "0" {
                return 0;
            }
            return 1;
        }
        let chars: Vec<char> = s.chars().collect();
        let length = chars.len();
        let mut dp = vec![0; s.len()];
        // 如果最后一个字符是'0', 则当前解法为0， 如果是其他字符则当前解法为1
        if chars[length-1] != '0' {
            dp[length-1] = 1
        } 
        // 判断倒数第二个字符的情况
        match chars[chars.len()-2] {
            // 为'0'的话， 则当前解法为0
            '0' => dp[length-2] = 0,
            // 为'1'的情况
            '1' => {
                // 如果最后一个字符为'0', 则当前解法为1, 因为'10'只有一种解法
                if chars[length-1] == '0' {
                    dp[length-2] = 1;
                } else {
                    // 其他字符的话， 则当前解法为2, e.g '12' => [ ['1', '2'], ['12'] ]
                    dp[length-2] = 2; 
                }
            },
            // 为'2'的情况
            '2' => {
                // 判断最后一个字符
                match chars[length-1] {
                    // e.g '28' => [ ['2', '8'] ]
                    '0' | '7' | '8' | '9' => dp[length-2] = 1,
                    // e.g '21' => [ ['2', '1'], ['21'] ]
                    _ => dp[length-2] = 2,
                }
            },
            // '3', '4'...'8', '9'
            _ =>  {
                // e.g '40' => invalid
                if chars[length-1] == '0' {
                    return 0;
                } else {
                    // e.g '36' => [ ['3', '6' ] ]
                    dp[length-2] = 1;
                }

            }
        }
        for i in (0..length-2).rev() {
            match chars[i] {
                '0' => dp[i] = 0,
                '1' => {
                    if chars[i+1] == '0' {
                        // e.g '10...' => [ ['10', ...] ]
                        dp[i] = dp[i+2];
                    } else {
                        // e.g '11...' => [ ['1', '1...'], ['11', ...] ]
                        dp[i] = dp[i+1] + dp[i+2];
                    }
                },
                '2' => {
                    match chars[i+1] {
                        // e.g '20...' => [ ['20', ...] ]
                        '0' => dp[i] = dp[i+2],
                        // e.g '27...' => [ ['2', '7...'] ]
                         '7' | '8' | '9' => dp[i] = dp[i+1],
                         // e.g '23...' => [ ['2', '3...'], ['23', ...] ]
                        _ => dp[i] = dp[i+1] + dp[i+2],
                    }
                },
                _ =>  {
                    // e.g '50' => invalid
                    if chars[i+1] == '0' {
                        return 0;
                    } else {
                        // e.g '6...'  => [ ['6', ...] ]
                        dp[i] = dp[i+1];
                    }
                }
            }
        }
        dp[0]
    }
}