欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode 91.Decode Ways

程序员文章站 2022-07-05 14:23:01
...

1. 题目概述

题目如下:
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.

Input: "12"
Output: 2
Explanation: It could be decoded as "AB" (1 2) or "L" (12).

题目的中文意思是给出一个字母和数字的映射,然后给出一串数字,返回对应的合法字母序列的个数.

2. 解题思路

首先用一个例子来分析一下.假设输入的数字是222,那么对应的输出结果是3.从左到右,只有2的时候对应的结果是1,22的时候对应的结果是2,分别为

2  2-> B B
22 -> V

222对应的结果是3,分别为

2 2 2-> B B B
22 2 -> V B
2 22 -> B V

在过程中我们可以发现

f(222) = f(22) + f(2)

所以很自然的想到动态规划.对于第i个数字子串对应的合法字母串数目,等于第i-1个子串和i-2个子串之和,如下所示

f[i] = f[i-1] + f[i-2]

接下来考虑特殊情况,假设输出的串为0,那么对应的输出应该为0,因为这个串无法映射到任意合法的字母串.所以我们知道,当起始字符串字母为0时,

f[1] = 0 if(s[0] == '0')

同理,接着考虑字符串28,这数字对应的合法字符串为1,如下所示

2 8 -> B F
28 -> None

28大于26,不对应任何字母.综上,我们可以得出完整的动态规划方程式

f[0] = 1
f[1] = (s[0] == '0')?0:1;
f[i] = (s[i]=='0')?0:f[i]+f[i-1]; //如果当前字母不为0,f[i]+=f[i-1]
f[i] = (s[i-1:s[i]] is valid) ?f[i]=f[i]+f[i-2]:0;//如果s[i-1:i]可以对应合法的字符串,f[i] = f[i] + f[i-2]

3. 题目代码

该题目的代码如下所示

#include <iostream>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    int numDecodings(string s) {
        if(s.size() == 0)return 0;
        if(s.size() == 1){
            if(s[0] == '0')return 0;
            else{
                return 1;
            }
        }
        vector<int> gV(s.size()+1,0);
        gV[0] = 1;
        if(s[0] == '0'){
            gV[1] = 0;
        }
        else{
            gV[1] = 1;
        }
        //for(int i=0;i<gV.size();i++)cout<<i<<" "<<gV[i]<<endl;

        for(int i=1;i<s.size();i++){
            if(s[i] != '0'){
                gV[i+1] += gV[i];
            }
            string sTemp = s.substr(i-1, 2);
            //cout<<sTemp<<endl;
            if(sTemp[0] != '0' && stoi(sTemp) > 0 && stoi(sTemp) <= 26){
                gV[i+1] += gV[i-1];
            }
        }
        return gV[s.size()];
    }
};

int main() {
    Solution se;
    cout<<se.numDecodings("")<<endl;
    cout<<se.numDecodings("01")<<endl;
    cout<<se.numDecodings("1")<<endl;
    cout<<se.numDecodings("11")<<endl;
    cout<<se.numDecodings("100")<<endl;
    cout<<se.numDecodings("226")<<endl;
    return 0;
}
相关标签: leetcode 算法