leetcode 91. Decode Ways DP动态规划 + 类似斐波那契序列 + DFS深度优先遍历

红太狼 2022-06-08 02:38 165阅读 0赞

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.

这道题考察的是解码，本质就是DFS深度优先遍历。不过网上看了一个基于DP的解决方法，也很简答。

建议和[leetcode 93. Restore IP Addresses DFS深度优先遍历][leetcode 93. Restore IP Addresses DFS] 和[leetcode 639. Decode Ways II 动态规划DP][leetcode 639. Decode Ways II _DP]一起学习，是一样的DFS深度优先遍历的做法

代码如下：

import java.util.Arrays;
    
    public class Solution
    {
        
        int res=0;
        public int numDecodings(String s)
        {
            if(s==null || s.length()<=0)
                return res;
    
            //DP 做法
            int []nums=new int[s.length()+1];
            //num[0]必须初始化为1
            nums[0]=1;
            nums[1]=s.charAt(0)=='0'? 0:1;
            //下面是动态规划去实现，
            for(int i=2;i<=s.length();i++)
            {
                if (s.charAt(i - 1) != '0')  
                    nums[i] = nums[i - 1];  
                if (s.charAt(i - 2) != '0' && Integer.parseInt("" + s.charAt(i - 2) + s.charAt(i - 1)) < 27)  
                    nums[i] += nums[i - 2];  
            } 
            return nums[s.length()];
        }
    
        private void getNum(String s, int index) 
        {
            if(index==s.length())
                res++;
            else
            {
                int a=(int)(s.charAt(index)-'0');
                if(a==0)
                    return;
    
                getNum(s, index+1);
                if(index+1 < s.length() && a<=2 && a*10+(int)(s.charAt(index+1)-'0')<=26)
                    getNum(s, index+2);
            }
        }
    }

下面是C++的做法，就是一个DP动态规划问题，这个和斐波那契额序列很像

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <unordered_map>
    #include <set>
    #include <unordered_set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    #include <iomanip>
    #include <cstdlib>
    #include <ctime>
    using namespace std;
    
    class Solution 
    {
    public:
        int numDecodings(string s) 
        {
            if (s.length() <= 0)
                return s.length();
            vector<int> dp(s.length() + 1, 0);
            dp[0] = 1;
            dp[1] = s[0]=='0'?0:1;
            for (int i = 2; i <= s.length(); i++)
            {
                if (s[i-1] != '0')
                    dp[i] = dp[i - 1];
                if (s[i - 2] != '0' && stoi(s.substr(i-2,2))<=26)
                    dp[i] += dp[i - 2];
            }
            return dp[s.length()];
        }
    };

[leetcode 93. Restore IP Addresses DFS]: http://blog.csdn.net/jackzhang_123/article/details/77943920
[leetcode 639. Decode Ways II _DP]: http://blog.csdn.net/jackzhang_123/article/details/78860230