资讯专栏INFORMATION COLUMN

LeetCode 394:字符串解码 Decode String

邹强 / 2106人阅读

摘要:用栈暂存的逻辑与递归基本一致,可以理解为用递归实现栈。没有栈这种数据结构,可以用数组或双端队列可以只用一个栈以元组的形式重复次数和字符串,如利用栈初始化数据结构递归字符串入栈刷新计算重复次数可直接操作字符串真的很方便。

题目:

给定一个经过编码的字符串,返回它解码后的字符串。
Given an encoded string, return its decoded string.

编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.

你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
You may assume that the input string is always valid; No extra white spaces, square brackets are well-formed, etc.

此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a2[4] 的输入。
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there won"t be input like 3a or 2[4].

示例:

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
解题思路:

​ 这道题类似我们之前做过的一道题:有效的括号: https://mp.weixin.qq.com/s/Sm1S26EgR-dC75hrhVnZGQ

只不过""有效的括号"" [] 内多了一些字符串需要操作。我们同样可以用数据结构栈来解题,,能用栈解决的题目大部分都可以用递归解决,两者逻辑基本相同:

输入:"3[a2[c]]"
初始化栈: 栈nums 存要重复的次数k,栈str 存字符串

遍历字符串:
指针指向字符"3",为数字
num暂存数字3

继续遍历,遇到字符"["
循环次数num入栈nums,空字符串res入栈str
nums: 3        res: ""
num置为0,str置空

继续遍历,遇到字符"a",为字母
空字符串res拼接字母"a",res="a"

继续遍历,遇到字符"2",为数字
num暂存数字2

继续遍历遇到字符"["
num入栈nums,res入栈str
nums: 3 -> 2    str: "" -> "a"
num置为0,str置空

继续遍历,遇到字符"c",为字母
空字符串res拼接字母"c",res="c"

继续遍历遇到字符"]"
nums弹出栈顶元素:当前字符串重复次数2
res = res*2 = "cc"
str弹出栈顶元素"a"与res拼接并入栈:
res = "a"+"cc"="acc"
str: "" -> "acc"

继续遍历遇到字符"]"
nums弹出栈顶元素:当前字符串重复次数3
res = res*3 = "accaccacc"
str弹出栈顶元素空字符串""与res拼接并入栈:
res=""+"accaccacc"="accaccacc"
str: "accaccacc"

结束返回res

注意:

由于重复次数可能大于10,所以暂存数字时要适当处理,如 num*10+当前数字

在c++里可以直接修改拼接字符,但Java不支持运算符重载,可以借助 StringBuilder 或 StringBuffer 类。

用栈暂存的逻辑与递归基本一致,可以理解为用递归实现栈。

python没有栈这种数据结构,可以用 list() 数组或双端队列 deque()

python可以只用一个栈以元组的形式重复次数和字符串,如(num,res)

利用栈:

Java:

class Solution {
    public String decodeString(String s) {
        //初始化数据结构
        Stack str = new Stack<>();
        Stack nums = new Stack<>();
        StringBuilder res = new StringBuilder();
        int num = 0;
        for (char c : s.toCharArray()) {//递归字符串
            if (c == "[") {
                str.push(res);//入栈
                nums.push(num);
                num = 0;//刷新num、res
                res = new StringBuilder();
            } else if (c == "]") {
                StringBuilder tmp = new StringBuilder();
                for (int i = nums.pop(); i > 0; i--) tmp.append(res);//res*3
                res = str.pop().append(tmp);
            } else if (c >= "0" && c <= "9") num = num * 10 + (c - "0");//计算重复次数
            else res.append(c);
        }
        return res.toString();
    }
}

Python:

可直接操作字符串真的很方便。py里有现成的判断字符串的方法:

isdigit() 是否为只包含数字的字符串

isalpha() 是否为只包含字母的字符串

class Solution:
    def decodeString(self, s: str) -> str:
        #初始化数据结构
        stack, res, num = [], "", 0
        for c in s:
            if c.isdigit():
                num = num * 10 + int(c)
            elif c.isalpha():
                res += c
            elif c == "[":
                #元组形式入栈
                stack.append((res, num))
                #刷新字符串和重复次数
                res, num = "", 0
            else:
                #如果c=="]",弹出字符串和重复次数
                last_str, this_num = stack.pop()
                res = last_str + this_num * res
        return res
利用递归:

Java:

将 s.length() 的值以参数传递,减少重复调用 length() 造成的时间损耗

class Solution {
    private int i = -1;//全局变量i,记录字符数组指针位置
    
    public String decodeString(String s) {
        return dfs(s.toCharArray(), s.length()).toString();
    }
    //递归函数
    private StringBuilder dfs(char[] chars, int len) {
        int num = 0;
        StringBuilder str = new StringBuilder();
        while (++i < len) {
            if (chars[i] >= "0" && chars[i] <= "9")
                num = num * 10 + (chars[i] - "0");
            else if (chars[i] == "[") {
                StringBuilder tmp = dfs(chars, len);//递归调用
                while (--num >= 0) str.append(tmp);//重复字符串res=res*num
                num = 0;
            } else if (chars[i] == "]") return str;
            else str.append(chars[i]);
        }
        return str;
    }
}

Python:

class Solution:
    i = -1
    #递归函数,可以直接操作字符串就无需再建一个dfs辅助函数
    def decodeString(self, s: str) -> str:
        res, num = "", 0
        while self.i < len(s) - 1:
            self.i += 1
            if s[self.i].isdigit():
                num = num * 10 + int(s[self.i])
            elif s[self.i].isalpha():
                res += s[self.i]
            elif s[self.i] == "[":
                #递归调用
                res += self.decodeString(s) * num
                num = 0
            elif s[self.i] == "]":
                return res
        return res

欢迎关注微.信公.众号:爱写Bug

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

转载请注明本文地址:https://www.ucloud.cn/yun/76126.html

相关文章

  • leetcode394. Decode String

    摘要:利用栈我们可以存储外围层已持有的字符串以及应当展开的次数。用栈的思路来写要求思路更加严谨,以免出现逻辑错误。这里需要额外注意的是,如果当前该括号外围存在父元素,则我们应当将父元素的计数和已有字符串压入栈中。 题目要求 Given an encoded string, return its decoded string. The encoding rule is: k[encoded_...

    Ilikewhite 评论0 收藏0
  • leetcode-394-Decode String

    摘要:原题核心是理解题意,总结规律,属于哪一类题目。完成从内往外层层解决,需要保持字符串的记忆。再加上列表操作和字符串追加的小技巧。应用栈的操作,保持一个字符串的状态,并可以从后往前进行处理。动态规划也可以。正则解法栈队列解法 原题: Given an encoded string, return its decoded string. The encoding rule is: k[enc...

    snifes 评论0 收藏0
  • LeetCode 394: DecodeString (Java)

    摘要:思路非常清晰,但是实现起来并不简单。得注意细节及其处理方式,比如数字可能出现两位及以上并列关系和包含关系如何巧妙区分。另外发现大循环用而不是可能更方便一些。 解码题。编码规则直接看例子(编码后字符串->原字符串):2[b] -> bb3[a2[c]] -> 3[acc] -> accaccacc2[a2[b]ef]xy ->2[abbef]xy->abbefabbefxy 根据上面的结...

    ccj659 评论0 收藏0
  • [Leetcode] Encode and Decode Strings 符串解码

    摘要:记录长度法复杂度时间空间思路本题难点在于如何在合并后的字符串中,区分出原来的每一个子串。这里我采取的编码方式,是将每个子串的长度先赋在前面,然后用一个隔开长度和子串本身。这样我们先读出长度,就知道该读取多少个字符作为子串了。 Encode and Decode Strings Design an algorithm to encode a list of strings to a s...

    gself 评论0 收藏0
  • [Leetcode] Decode Ways 解码方式

    摘要:最新更新请见动态规划复杂度时间空间思路解码是有规律的,所以我们可以尝试动态规划。如果字符串的第位和第位不能组成有效二位数字,而且第位不是的话,说明我们是在第位的解码方法上继续解码。 Decode Ways 最新更新请见:https://yanjia.me/zh/2019/02/... A message containing letters from A-Z is being en...

    animabear 评论0 收藏0

发表评论

0条评论

最新活动
阅读需要支付1元查看
<