leetcode-394-Decode String

snifes 发布于2019-07-30 17:38 / 1563人阅读

摘要：原题核心是理解题意，总结规律，属于哪一类题目。完成从内往外层层解决，需要保持字符串的记忆。再加上列表操作和字符串追加的小技巧。应用栈的操作，保持一个字符串的状态，并可以从后往前进行处理。动态规划也可以。正则解法栈队列解法

原题：
 Given an encoded string, return it"s decoded string.
 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.
 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].
 Examples:

s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".

核心是理解题意，总结规律，属于哪一类题目。 此题的规律在于 嵌套组合(数字+字母), 而且从dp的角度看，每消除一个底层【】，就会形成一个新的底层【】。
  所以规律是 解决 最里侧的【】。如此往复。 
  完成从内往外层层解决【】，需要保持字符串的记忆。stack可以完成。 再加上列表操作和字符串追加的小技巧。
  应用：栈的操作，保持一个字符串的状态，并可以从后往前进行处理。
  记忆时间的先后顺序， stack可以完成。 动态规划也可以。
  思考问题可以从前往后考虑解决办法，也可以从后往前考虑，如果不能线性找到解决整体的办法，就采用动态规划的思想，找到解决局部问题的方法。

正则解法：
import re
class Solution:
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        pattern=re.compile("(d+)[([a-zA-Z]+)]")
        while "[" in s:
            result_tmp=pattern.search(s)
            print(result_tmp.groups())
            # if result_tmp:
            #     for freq,dst in result_tmp.group():
            freq,dst = result_tmp.groups()
            dst_str=dst*int(freq)
            # print(dst)
            s=pattern.sub(dst_str,s)
            # print(dst,s)
        return s
if __name__=="__main__":
    s = "3[a]2[bc]"
    s = "3[a2[c]]"
    s="3[a]2[bc]"
    s="3[a]2[b4[F]c]"
    s="2[ab3[cd]]4[xy]"
    st=Solution()
    out=st.decodeString(s)
    print(out)

栈队列解法：
class Solution:
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        stack=[[1,""]]
        final_str=""
        num=""
        for char_iter in s:
            if char_iter.isdigit():
                num+=char_iter
                # stack.append([char_iter,""])
            elif char_iter=="[":
                stack.append([int(num),""])
                num=""
            elif char_iter.isalpha():
                stack[-1][-1]+=char_iter
            elif char_iter=="]":
                # print(stack)
                freq_chars=stack.pop()
                # print(freq_chars)
                str_tmp=freq_chars[1]*int(freq_chars[0])
                stack[-1][-1]+=str_tmp
            else:
                stack[0][-1]+=str_tmp
        # print(final_str)
        # print(stack)
        return stack[0][1]


if __name__=="__main__":
    s = "3[a]2[bc]"
    s = "3[a2[c]]"
    s="3[a]2[bc]"
    s="3[a]2[b4[F]c]"
    s="2[ab3[cd]]4[xy]"
    s=""2[abc]3[cd]ef""
    s="100[leetcode]"
    st=Solution()
    out=st.decodeString(s)
    print(out)

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

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

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
Python 字符串内置方法

摘要：字符串内置方法作者博客返回字符串的第一个大写字母。将序列中的元素字符串合并连接到一个字符串，作为分隔符。根据分隔符如果没有提供默认为空格分割并返回子串的列表如果给定了，则最多分为个子串。 Python 字符串内置方法作者博客：http://zzir.cn/ string.capitalize() 返回字符串的第一个大写字母。 string.centr(width) 返回一个共 wid...

tracymac7 2019-07-25 10:45 评论0 收藏0
Java String类笔记

摘要：这两个操作符都是编译器默认引入了类，最后都调用方法返回对象，临时对象被回收，因此效率极为低下 Java String类笔记声明文章均为本人技术笔记，转载请注明出处https://segmentfault.com/u/yzwall String的不可变性 String的不可变性 // String declaration public final class String ...

Vicky 2019-08-14 18:06 评论0 收藏0
面试别再问我String了

摘要：阅读原文面试别再问我了字符串广泛应用在编程中，在中字符串属于对象，提供了类来创建和操作字符串。测试此字符串是否以指定的后缀结束。当执行此句时，因为对应的实例已经存在于字符串常量池中，所以会将此实例复制到会在堆中并返回引用地址。阅读原文：面试别再问我String了字符串广泛应用在Java 编程中，在 Java 中字符串属于对象，Java 提供了 String 类来创建和操作字符串。...

leon 2019-08-16 16:14 评论0 收藏0
Java String、StringBuffer和StringBuilder类

摘要：可以调用方法将其转换为一个对象是线程安全的，则没有实现线程安全功能，所以性能略高。通过串联更方便将该对象与的对象进行比较。追加字符串插入替换删除反转输出输出改变的长度，将只保留前面部分 String类是不可变类，即一旦一个String对象被创建以后，包括在这个对象中的字符序列是不可改变的，直至这个对象被销毁 StringBuffer对象则代表一个字符序列可变的字符串，当一个String...

Jason 2019-08-14 16:58 评论0 收藏0