[Leetcode] 155. Decode String

문제

https://leetcode.com/problems/decode-string/description/?envType=study-plan-v2&envId=top-100-liked

풀이

혼자 힘으로 해결하지 못해 discussion을 보고 풀이를 이해하기 위해 노력했다.
특히 이 풀이를 참조했다.

class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        current_string = ""
        k = 0

        for char in s:
            if char == "[":
                stack.append((current_string, k)) # 지금까지만든 문자열, 뒤에서 만들어질 문자열에 곱할 값
                current_string = ""
                k = 0
            elif char == "]":
                last_string, last_k = stack.pop()
                current_string = last_string + last_k * current_string # 시간복잡도?
            elif char.isdigit():
                k = k*10 + int(char) # 2자리 이상일 수 있으니
            else:
                current_string += char
        
        return current_string

이때 current_string = last_string + last_k * current_string 을 고려한 시간복잡도를 계산하려 했는데 정확히 어떤 값이 나와야 하는지는 모르겠다