資訊專欄INFORMATION COLUMN
摘要：原題核心是理解題意，總結(jié)規(guī)律，屬于哪一類題目。完成從內(nèi)往外層層解決，需要保持字符串的記憶。再加上列表操作和字符串追加的小技巧。應(yīng)用棧的操作，保持一個字符串的狀態(tài)，并可以從后往前進行處理。動態(tài)規(guī)劃也可以。正則解法棧隊列解法
原題：
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".
核心是理解題意，總結(jié)規(guī)律，屬于哪一類題目。 此題的規(guī)律在于 嵌套組合(數(shù)字+字母), 而且從dp的角度看，每消除一個底層【】，就會形成一個新的底層【】。
所以規(guī)律是 解決 最里側(cè)的【】。如此往復(fù)。
完成從內(nèi)往外層層解決【】，需要保持字符串的記憶。stack可以完成。 再加上列表操作和字符串追加的小技巧。
應(yīng)用：棧的操作，保持一個字符串的狀態(tài)，并可以從后往前進行處理。
記憶時間的先后順序， stack可以完成。 動態(tài)規(guī)劃也可以。
思考問題可以從前往后考慮解決辦法，也可以從后往前考慮，如果不能線性找到解決整體的辦法，就采用動態(tài)規(guī)劃的思想，找到解決局部問題的方法。
正則解法：
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)
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/42323.html
摘要：利用棧我們可以存儲外圍層已持有的字符串以及應(yīng)當(dāng)展開的次數(shù)。用棧的思路來寫要求思路更加嚴謹，以免出現(xiàn)邏輯錯誤。這里需要額外注意的是，如果當(dāng)前該括號外圍存在父元素，則我們應(yīng)當(dāng)將父元素的計數(shù)和已有字符串壓入棧中。 題目要求 Given an encoded string, return its decoded string. The encoding rule is: k[encoded_...
摘要：字符串內(nèi)置方法作者博客返回字符串的第一個大寫字母。將序列中的元素字符串合并連接到一個字符串，作為分隔符。根據(jù)分隔符如果沒有提供默認為空格分割并返回子串的列表如果給定了，則最多分為個子串。 Python 字符串內(nèi)置方法 作者博客：http://zzir.cn/ string.capitalize() 返回字符串的第一個大寫字母。 string.centr(width) 返回一個共 wid...
摘要：這兩個操作符都是編譯器默認引入了類，最后都調(diào)用方法返回對象，臨時對象被回收，因此效率極為低下 Java String類筆記 聲明 文章均為本人技術(shù)筆記，轉(zhuǎn)載請注明出處https://segmentfault.com/u/yzwall String的不可變性 String的不可變性 // String declaration public final class String ...
摘要：閱讀原文面試別再問我了字符串廣泛應(yīng)用在編程中，在中字符串屬于對象，提供了類來創(chuàng)建和操作字符串。測試此字符串是否以指定的后綴結(jié)束。當(dāng)執(zhí)行此句時，因為對應(yīng)的實例已經(jīng)存在于字符串常量池中，所以會將此實例復(fù)制到會在堆中并返回引用地址。 閱讀原文：面試別再問我String了 字符串廣泛應(yīng)用 在Java 編程中，在 Java 中字符串屬于對象，Java 提供了 String 類來創(chuàng)建和操作字符串。...
摘要：可以調(diào)用方法將其轉(zhuǎn)換為一個對象是線程安全的，則沒有實現(xiàn)線程安全功能，所以性能略高。通過串聯(lián)更方便將該對象與的對象進行比較。追加字符串插入替換刪除反轉(zhuǎn)輸出輸出改變的長度，將只保留前面部分 String類是不可變類，即一旦一個String對象被創(chuàng)建以后，包括在這個對象中的字符序列是不可改變的，直至這個對象被銷毀 StringBuffer對象則代表一個字符序列可變的字符串，當(dāng)一個String...
閱讀 3385·2021-11-22 12:04
閱讀 2771·2019-08-29 13:49
閱讀 534·2019-08-26 13:45
閱讀 2322·2019-08-26 11:56
閱讀 1069·2019-08-26 11:43
閱讀 648·2019-08-26 10:45
閱讀 1330·2019-08-23 16:48
閱讀 2231·2019-08-23 16:07
