LeetCode开心刷题三十五——91. Decode Ways

梦里梦外; 2023-08-17 15:14 102阅读 0赞

91. Decode Ways

Medium

15501793FavoriteShare

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).
    
    BONUS：
    MAIN IDEA：
    假 if not 表达式 else 真
    表达式真假决定执行哪部分

#if not 为假返回if not前面内容，否则返回0
    exp3 = lambda x:x+1 if not 2==1 else 0
    print(exp3(2))
    
    
    exp4 = lambda x:x+1 if not 1==1 else 0
    print(exp4(2))

C++ Code：
    Scroll Array DP：

#include<stdio.h>
    #include<iostream>
    #include<string>
    #include<vector>
    #include<set>
    #include<map>
    #include<algorithm>
    #include<stack>
    #include<climits>
    //
    using namespace std;
    //similar to the idea of scrolling array
    class Solution
    {
    public:
        int numDecodings(string s)
        {
            //NULL
            if(s.empty()||s[0]=='0') return 0;
            //length like empty is function don't forget()
            if(s.length()==1) return 1;
            //Judge
            const int n=s.length();
            //store scrolling variable
            int w1=1,w2=1;
            //main
            for(int i=1;i<n;i++)
            {
                //inner variable every loop reset
                int w=0;
                if(!isValid(s[i])&&!isValid(s[i-1],s[i])) return 0;
                if(isValid(s[i])) w=w1;
                if(isValid(s[i-1],s[i])) w+=w2;
                //w1---->dp[i-1] w2--->dp[i-2] after loop i->i+1 other index also change
                //scrolling variable
                w2=w1;
                w1=w;
            }
            return w1;
        }
    private:
        bool isValid(const char c)
        {
            return c!='0';
        }
        bool isValid(const char c1,const char c2)
        {
            const int num=(c1-'0')*10+(c2-'0');
            //directly return expression
            return num>9&&num<27;
        }
    };
    
    int main()
    {
        string res="226";
        Solution s;
        cout<<s.numDecodings(res)<<endl;
        return 0;
    }

C++ version:

index recursion O(N)

class Solution
    {
    public:
        int numDecodings(string s)
        {
            if(s.empty()) return 0;
            return clac(s,0,s.length()-1);
        }
    private:
        int clac(const string& s,int l,int r)
        {
            if(w_map.count(l)) return w_map[l];
            if(s[l]=='0') return 0;
            if(l>=r) return 1;
    
            int w=clac(s,l+1,r);
            //-'0' easy forget
            const int tmp=(s[l]-'0')*10+(s[l+1]-'0');
    
            if(tmp>9&&tmp<27)
            {
                w+=clac(s,l+2,r);
            }
            w_map[l]=w;
            return w;
    
        }
        unordered_map<int,int> w_map;
    
    };

C++ version:

full string recursion O(N^2)

traversing the string increases the duration

BONUS:substr usage

substr(i):string past i include i substr(2) 34567

substr(1,2):from 1->2

substr函数的形式为s.substr(pos, n)，  
需要两个参数，第一个是开始位置，第二个是获取子串的长度。

string s="1234567";
        cout<<" 1 "<<s.substr(2)<<" 2 "<<s.substr(1,2)<<endl;
        //result
        1 34567 2 23

Python Version:

class Solution(object):
        def numDecodings(self, s):
            """
            :type s: str
            :rtype: int
            """
            dp = [0] * (len(s) + 1)
            dp[0] = 1
    　　　　　#if instead len(s)+1 into len(dp) will lower
            for i in range(1, len(s)+1):
                if s[i-1] != '0':
                    dp[i] = dp[i-1]
                if i != 1 and '09' < s[i-2:i] < '27':
                    dp[i] += dp[i-2]
            return dp[-1]
    
    solu=Solution()
    print(solu.numDecodings(s="226"))

转载于:https://www.cnblogs.com/Marigolci/p/11352015.html