快捷導(dǎo)航

C++實(shí)現(xiàn)LeetCode(91.解碼方法)

更新時(shí)間：2021年07月19日 10:40:58 作者：Grandyang

這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(91.解碼方法),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

[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 非常的相似，但是還有一些其他的限制條件，比如說(shuō)一位數(shù)時(shí)不能為0，兩位數(shù)不能大于 26，其十位上的數(shù)也不能為0，除去這些限制條件，跟爬梯子基本沒(méi)啥區(qū)別，也勉強(qiáng)算特殊的斐波那契數(shù)列，當(dāng)然需要用動(dòng)態(tài)規(guī)劃 Dynamci Programming 來(lái)解。建立一維 dp 數(shù)組，其中 dp[i] 表示s中前i個(gè)字符組成的子串的解碼方法的個(gè)數(shù)，長(zhǎng)度比輸入數(shù)組長(zhǎng)多多1，并將 dp[0] 初始化為1。現(xiàn)在來(lái)找狀態(tài)轉(zhuǎn)移方程，dp[i] 的值跟之前的狀態(tài)有著千絲萬(wàn)縷的聯(lián)系，就拿題目中的例子2來(lái)分析吧，當(dāng) i=1 時(shí)，對(duì)應(yīng)s中的字符是 s[0]='2'，只有一種拆分方法，就是2，注意 s[0] 一定不能為0，這樣的話無(wú)法拆分。當(dāng) i=2 時(shí)，對(duì)應(yīng)s中的字符是 s[1]='2'，由于 s[1] 不為0，那么其可以被單獨(dú)拆分出來(lái)，就可以在之前 dp[i-1] 的每種情況下都加上一個(gè)單獨(dú)的2，這樣 dp[i] 至少可以有跟 dp[i-1] 一樣多的拆分情況，接下來(lái)還要看其能否跟前一個(gè)數(shù)字拼起來(lái)，若拼起來(lái)的兩位數(shù)小于等于26，并且大于等于 10（因?yàn)閮晌粩?shù)的高位不能是0），那么就可以在之前 dp[i-2] 的每種情況下都加上這個(gè)二位數(shù)，所以最終 dp[i] = dp[i-1] + dp[i-2]，是不是發(fā)現(xiàn)跟斐波那契數(shù)列的性質(zhì)吻合了。所以0是個(gè)很特殊的存在，若當(dāng)前位置是0，則一定無(wú)法單獨(dú)拆分出來(lái)，即不能加上 dp[i-1]，就只能看否跟前一個(gè)數(shù)字組成大于等于 10 且小于等于 26 的數(shù)，能的話可以加上 dp[i-2]，否則就只能保持為0了。具體的操作步驟是，在遍歷的過(guò)程中，對(duì)每個(gè)數(shù)字首先判斷其是否為0，若是則將 dp[i] 賦為0，若不是，賦上 dp[i-1] 的值，然后看數(shù)組前一位是否存在，如果存在且滿足前一位是1，或者和當(dāng)前位一起組成的兩位數(shù)不大于 26，則當(dāng)前 dp[i] 值加上 dp[i - 2]。最終返回 dp 數(shù)組的最后一個(gè)值即可，代碼如下：

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()];
    }
}

我們?cè)賮?lái)看一種空間復(fù)雜度為 O(1) 的解法，用兩個(gè)變量 a, b 來(lái)分別表示 s[i-1] 和 s[i-2] 的解碼方法，然后從 i=1 開始遍歷，也就是字符串的第二個(gè)字符，判斷如果當(dāng)前字符為 '0'，說(shuō)明當(dāng)前字符不能單獨(dú)拆分出來(lái)，只能和前一個(gè)字符一起，先將 a 賦為0，然后看前面的字符，如果前面的字符是1或者2時(shí)，就可以更新 a = a + b，然后 b = a - b，其實(shí) b 賦值為之前的 a，如果不滿足這些條件的話，那么 b = a，參見(jiàn)代碼如下：

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;
    }
}

到此這篇關(guān)于C++實(shí)現(xiàn)LeetCode(91.解碼方法)的文章就介紹到這了,更多相關(guān)C++實(shí)現(xiàn)解碼方法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: