leetcode-91-Decode Ways

sihai 發布于2019-07-31 11:05 / 2567人閱讀

摘要：經總結，發現當前字符前面的兩個字符和一個字符可以拿出來進行分析。當前的數目可以作為和的數目的疊加。所以關系式是其他的特殊情況可以進行特殊處理。需要注意的是如果錢兩位是，，則這兩位作廢，不能計入其他情況的統計，即。

描述

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.

class Solution:
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        if not s:
            return 0
        if s[0]=="0" :
            return 0
        elif len(s)==1:
            return 1

        length=len(s)
        dp=[0 for _ in range(length+1)]
        print("dp:==>",dp)
        dp[0]=1
        dp[1]=1
        for i in range(2,length+1):
            l2=int(s[i-2:i])
            l1=int(s[i-1:i])
            if 10",dp)
        out=dp[length]
        return out
if __name__=="__main__":
    st=Solution()
    num="2626"
    num="0"
    num="11"
    num="1"
    num="0"
    num="11"
    num="110"
    out=st.numDecodings(num)
    print(out)

解釋：本地是動態規劃解決，所以需要分清楚往后疊加增加字符時的數目之間的變化規律。經總結，發現當前字符前面的兩個字符和一個字符可以拿出來進行分析。當前的數目可以作為cur_index-2和cur_index-1的數目的疊加。只跟前兩個位置的字符處產生的數目有關系。
所以dp關系式是：dp[n]=dp[n-1]+dp[n-2].其他的特殊情況可以進行特殊處理。比如10，20，位數為1的情況。需要注意的是：如果錢兩位是10，20，則這兩位作廢，不能計入其他情況的統計，即 dp[i]=dp[i-2]。

云服務器 GPU云服務器 Ways

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

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

【Leetcode】62. 不同路徑

摘要：作者碼蹄疾畢業于哈爾濱工業大學。機器人試圖達到網格的右下角在下圖中標記為。問總共有多少條不同的路徑例如，上圖是一個的網格。有多少可能的路徑說明和的值均不超過。示例輸入輸出解釋從左上角開始，總共有條路徑可以到達右下角。作者: 碼蹄疾畢業于哈爾濱工業大學。小米廣告第三代廣告引擎的設計者、開發者；負責小米應用商店、日歷、開屏廣告業務線研發；主導小米廣告引擎多個模塊重構；關注推薦、搜索、廣...

LMou 2019-08-19 11:07 評論0 收藏0
【Leetcode】62. 不同路徑

摘要：作者碼蹄疾畢業于哈爾濱工業大學。機器人試圖達到網格的右下角在下圖中標記為。問總共有多少條不同的路徑例如，上圖是一個的網格。有多少可能的路徑說明和的值均不超過。示例輸入輸出解釋從左上角開始，總共有條路徑可以到達右下角。作者: 碼蹄疾畢業于哈爾濱工業大學。小米廣告第三代廣告引擎的設計者、開發者；負責小米應用商店、日歷、開屏廣告業務線研發；主導小米廣告引擎多個模塊重構；關注推薦、搜索、廣...

canopus4u 2019-07-30 17:46 評論0 收藏0
[Leetcode] Decode Ways 解碼方式

摘要：最新更新請見動態規劃復雜度時間空間思路解碼是有規律的，所以我們可以嘗試動態規劃。如果字符串的第位和第位不能組成有效二位數字，而且第位不是的話，說明我們是在第位的解碼方法上繼續解碼。 Decode Ways 最新更新請見：https://yanjia.me/zh/2019/02/... A message containing letters from A-Z is being en...

animabear 2019-08-14 12:38 評論0 收藏0