C++實現LeetCode(91.解碼方法)

Posted on by

[LeetCode] 91. Decode Ways 解碼方法

A message containing letters from A-Z is being encoded to numbers using the following mapping:

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

Given a non-empty string containing only digits, determine the total number of ways to decode it.

Example 1:

Input: “12”
Output: 2
Explanation: It could be decoded as “AB” (1 2) or “L” (12).

Example 2:

Input: “226”
Output: 3
Explanation: It could be decoded as “BZ” (2 26), “VF” (22 6), or “BBF” (2 2 6).

這道題要求解碼方法，跟之前那道 Climbing Stairs 非常的相似，但是還有一些其他的限制條件，比如說一位數時不能為0，兩位數不能大於 26，其十位上的數也不能為0，除去這些限制條件，跟爬梯子基本沒啥區別，也勉強算特殊的斐波那契數列，當然需要用動態規劃 Dynamci Programming 來解。建立一維 dp 數組，其中 dp[i] 表示s中前i個字符組成的子串的解碼方法的個數，長度比輸入數組長多多1，並將 dp[0] 初始化為1。現在來找狀態轉移方程，dp[i] 的值跟之前的狀態有著千絲萬縷的聯系，就拿題目中的例子2來分析吧，當 i=1 時，對應s中的字符是 s[0]=’2’，隻有一種拆分方法，就是2，註意 s[0] 一定不能為0，這樣的話無法拆分。當 i=2 時，對應s中的字符是 s[1]=’2’，由於 s[1] 不為0，那麼其可以被單獨拆分出來，就可以在之前 dp[i-1] 的每種情況下都加上一個單獨的2，這樣 dp[i] 至少可以有跟 dp[i-1] 一樣多的拆分情況，接下來還要看其能否跟前一個數字拼起來，若拼起來的兩位數小於等於26，並且大於等於 10（因為兩位數的高位不能是0），那麼就可以在之前 dp[i-2] 的每種情況下都加上這個二位數，所以最終 dp[i] = dp[i-1] + dp[i-2]，是不是發現跟斐波那契數列的性質吻合瞭。所以0是個很特殊的存在，若當前位置是0，則一定無法單獨拆分出來，即不能加上 dp[i-1]，就隻能看否跟前一個數字組成大於等於 10 且小於等於 26 的數，能的話可以加上 dp[i-2]，否則就隻能保持為0瞭。具體的操作步驟是，在遍歷的過程中，對每個數字首先判斷其是否為0，若是則將 dp[i] 賦為0，若不是，賦上 dp[i-1] 的值，然後看數組前一位是否存在，如果存在且滿足前一位是1，或者和當前位一起組成的兩位數不大於 26，則當前 dp[i] 值加上 dp[i – 2]。最終返回 dp 數組的最後一個值即可，代碼如下：

C++ 解法一：

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        vector<int> dp(s.size() + 1, 0);
        dp[0] = 1;
        for (int i = 1; i < dp.size(); ++i) {
            dp[i] = (s[i - 1] == '0') ? 0 : dp[i - 1];
            if (i > 1 && (s[i - 2] == '1' || (s[i - 2] == '2' && s[i - 1] <= '6'))) {
                dp[i] += dp[i - 2];
            }
        }
        return dp.back();
    }
};

Java 解法一：

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; ++i) {
            dp[i] = (s.charAt(i - 1) == '0') ? 0 : dp[i - 1];
            if (i > 1 && (s.charAt(i - 2) == '1' || (s.charAt(i - 2) == '2' && s.charAt(i - 1) <= '6'))) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length()];
    }
}

下面這種方法跟上面的方法的思路一樣，隻是寫法略有不同：

C++ 解法二：

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        vector<int> dp(s.size() + 1, 0);
        dp[0] = 1;
        for (int i = 1; i < dp.size(); ++i) {
            if (s[i - 1] != '0') dp[i] += dp[i - 1];
            if (i >= 2 && s.substr(i - 2, 2) <= "26" && s.substr(i - 2, 2) >= "10") {
                dp[i] += dp[i - 2];
            }
        }
        return dp.back();
    }
};

Java  解法二：

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int[] dp = new int[s.length() + 1];
        dp[0] = 1;
        for (int i = 1; i < dp.length; ++i) {
            if (s.charAt(i - 1) != '0') dp[i] += dp[i - 1];
            if (i >= 2 && (s.substring(i - 2, i).compareTo("10") >= 0 && s.substring(i - 2, i).compareTo("26") <= 0)) {
                dp[i] += dp[i - 2];
            }
        }
        return dp[s.length()];
    }
}

我們再來看一種空間復雜度為 O(1) 的解法，用兩個變量 a, b 來分別表示 s[i-1] 和 s[i-2] 的解碼方法，然後從 i=1 開始遍歷，也就是字符串的第二個字符，判斷如果當前字符為 ‘0’，說明當前字符不能單獨拆分出來，隻能和前一個字符一起，先將 a 賦為0，然後看前面的字符，如果前面的字符是1或者2時，就可以更新 a = a + b，然後 b = a – b，其實 b 賦值為之前的 a，如果不滿足這些條件的話，那麼 b = a，參見代碼如下：

C++ 解法三：

class Solution {
public:
    int numDecodings(string s) {
        if (s.empty() || s[0] == '0') return 0;
        int a = 1, b = 1, n = s.size();
        for (int i = 1; i < n; ++i) {
            if (s[i] == '0') a = 0;
            if (s[i - 1] == '1' || (s[i - 1] == '2' && s[i] <= '6')) {
                a = a + b;
                b = a - b;
            } else {
                b = a;
            }
        }
        return a;
    }
};

Java 解法三：

class Solution {
    public int numDecodings(String s) {
        if (s.isEmpty() || s.charAt(0) == '0') return 0;
        int a = 1, b = 1, n = s.length();
        for (int i = 1; i < n; ++i) {
            if (s.charAt(i) == '0') a = 0;
            if (s.charAt(i - 1) == '1' || (s.charAt(i - 1) == '2' && s.charAt(i) <= '6')) {
                a = a + b;
                b = a - b;
            } else {
                b = a;
            }
        }
        return a;
    }
}

到此這篇關於C++實現LeetCode(91.解碼方法)的文章就介紹到這瞭,更多相關C++實現解碼方法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：