[Leetcode] Decode Ways 解码方式

animabear 发布于2019-08-14 12:38 / 1651人阅读

摘要：最新更新请见动态规划复杂度时间空间思路解码是有规律的，所以我们可以尝试动态规划。如果字符串的第位和第位不能组成有效二位数字，而且第位不是的话，说明我们是在第位的解码方法上继续解码。

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

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/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