Python solution with detailed explanation


  • 0
    G

    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)
    

Log in to reply
 

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