Python solution with detailed explanation

• Solution with discussion https://discuss.leetcode.com/topic/73523/python-solution-with-detailed-explanation

Decode String https://leetcode.com/problems/decode-string/

Stack Based Solution: TimeO(N) and Space O(N)

• Use a stack to solve this problem.
• If we encounter a digit,figure out the entire number and push to stack.
• If we encounter a character, figure out the enture work and push on the stack.
• If we encounter a "[", just push on stack.
• If we encounter "]", we first figure our the text and then its repetition count. We then create the concatenated text and push on stack.

Interesting Examples: Careful while counting num repetitions

• "3[a]2[bc]" implies we need to return "".join(st) and not st[-1]. This example shows we will have "aaa" and "bcbc" on stack after the loop terminates.

Code

``````from collections import deque
class Solution(object):
def decodeString(self, s):
"""
:type s: str
:rtype: str
"""
if not s:
return ""
st, end = [], 0
while end < len(s):
if s[end].isdigit():
num = 0
while end < len(s) and s[end].isdigit():
num = num*10 + int(s[end])
end += 1
st.append(num)
elif s[end] == "[":
st.append("[")
end += 1
elif s[end].isalpha():
temp = []
while end < len(s) and s[end].isalpha():
temp.append(s[end])
end += 1
st.append("".join(temp))
elif s[end] == "]":
x = deque()
while st[-1] != "[":
x.appendleft(st[-1])
st.pop()
st.pop()
if st and type(st[-1]) is int:
temp_str = "".join(x) * st[-1]
st.pop()
st.append(temp_str)
end += 1
return "".join(st)
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.