leetcode-394-Decode String

snifes 發布于2019-07-30 17:38 / 1564人閱讀

摘要：原題核心是理解題意，總結規律，屬于哪一類題目。完成從內往外層層解決，需要保持字符串的記憶。再加上列表操作和字符串追加的小技巧。應用棧的操作，保持一個字符串的狀態，并可以從后往前進行處理。動態規劃也可以。正則解法棧隊列解法

原題：
 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)

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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