[Leetcode] Decode Ways 解碼方式

animabear 發布于2019-08-14 12:38 / 1652人閱讀

摘要：最新更新請見動態規劃復雜度時間空間思路解碼是有規律的，所以我們可以嘗試動態規劃。如果字符串的第位和第位不能組成有效二位數字，而且第位不是的話，說明我們是在第位的解碼方法上繼續解碼。

Decode Ways 最新更新請見：https://yanjia.me/zh/2019/02/...

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

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

Given an encoded message containing digits, determine the total number of ways to decode it.

For example, Given encoded message "12", it could be decoded as "AB"
(1 2) or "L" (12).

The number of ways decoding "12" is 2.

動態規劃 復雜度

時間 O(N) 空間 O(N)

思路

解碼是有規律的，所以我們可以嘗試動態規劃。假設數組dp[i]表示從頭到字符串的第i位，一共有多少種解碼方法的話，那么如果字符串的第i-1位和第i位能組成一個10到26的數字，說明我們是在第i-2位的解碼方法上繼續解碼。如果字符串的第i-1位和第i位不能組成有效二位數字，而且第i位不是0的話，說明我們是在第i-1位的解碼方法上繼續解碼。所以，如果兩個條件都符合，則dp[i]=dp[i-1]+dp[i-2]，否則dp[i]=dp[i-1]。

注意

如果出現無法被兩位數接納的0，則無法解碼，我們可以在一開始就判斷，并將其初始化為0，這樣后面的相加永遠都是加0

代碼

public class Solution {
    public int numDecodings(String s) {
        if(s.length() == 0) return s.length();
        int[] dp = new int[s.length() + 1];
        // 初始化第一種解碼方式
        dp[0] = 1;
        // 如果第一位是0，則無法解碼
        dp[1] = s.charAt(0) == "0" ? 0 : 1;
        for(int i = 2; i <= s.length(); i++){
            // 如果字符串的第i-1位和第i位能組成一個10到26的數字，說明我們可以在第i-2位的解碼方法上繼續解碼
            if(Integer.parseInt(s.substring(i-2, i)) <= 26 && Integer.parseInt(s.substring(i-2, i)) >= 10){
                dp[i] += dp[i - 2];
            }
            // 如果字符串的第i-1位和第i位不能組成有效二位數字，在第i-1位的解碼方法上繼續解碼
            if(Integer.parseInt(s.substring(i-1, i)) != 0){
                dp[i] += dp[i - 1];
            }
        }
        return dp[s.length()];
    }
}

云服務器 GPU云服務器 Ways LeetCode decode LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/64607.html

[LintCode/LeetCode] Decode Ways [String to Integer

摘要：用將子字符串轉化為，參見和的區別然后用動規方法表示字符串的前位到包含方法的個數。最后返回對應字符串末位的動規結果。 Problem A message containing letters from A-Z is being encoded to numbers using the following mapping: A -> 1 B -> 2 ... Z -> 26 Given ...

andong777 2019-08-14 15:44 評論0 收藏0
leetcode-91-Decode Ways

摘要：經總結，發現當前字符前面的兩個字符和一個字符可以拿出來進行分析。當前的數目可以作為和的數目的疊加。所以關系式是其他的特殊情況可以進行特殊處理。需要注意的是如果錢兩位是，，則這兩位作廢，不能計入其他情況的統計，即。描述 A message containing letters from A-Z is being encoded to numbersusing the following...

sihai 2019-07-31 11:05 評論0 收藏0
[Leetcode] Encode and Decode Strings 字符串編解碼

摘要：記錄長度法復雜度時間空間思路本題難點在于如何在合并后的字符串中，區分出原來的每一個子串。這里我采取的編碼方式，是將每個子串的長度先賦在前面，然后用一個隔開長度和子串本身。這樣我們先讀出長度，就知道該讀取多少個字符作為子串了。 Encode and Decode Strings Design an algorithm to encode a list of strings to a s...

gself 2019-08-14 12:36 評論0 收藏0
LeetCode 394：字符串解碼 Decode String

摘要：用棧暫存的邏輯與遞歸基本一致，可以理解為用遞歸實現棧。沒有棧這種數據結構，可以用數組或雙端隊列可以只用一個棧以元組的形式重復次數和字符串，如利用棧初始化數據結構遞歸字符串入棧刷新計算重復次數可直接操作字符串真的很方便。題目：給定一個經過編碼的字符串，返回它解碼后的字符串。Given an encoded string, return its decoded string. 編碼規則...

鄒強 2019-08-19 10:30 評論0 收藏0
leetcode394. Decode String

摘要：利用棧我們可以存儲外圍層已持有的字符串以及應當展開的次數。用棧的思路來寫要求思路更加嚴謹，以免出現邏輯錯誤。這里需要額外注意的是，如果當前該括號外圍存在父元素，則我們應當將父元素的計數和已有字符串壓入棧中。題目要求 Given an encoded string, return its decoded string. The encoding rule is: k[encoded_...

Ilikewhite 2019-08-16 15:04 評論0 收藏0