394.md

394. Decode String

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/decode-string/

内容描述

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".

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

就很像一个basic calculator，224题

iterative, 栈

beats 100%

class Solution:
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s or len(s) == 0:
            return ''
        stack = [['', 1]]
        num = 0
        for i, c in enumerate(s):
            if c.isdigit():
                num = num * 10 + int(c)
            elif c.isalpha():
                stack[-1][0] += c
            elif c == '[':
                stack.append(['', num])
                num = 0
            elif c == ']':
                prev_str, cnt = stack.pop()
                stack[-1][0] += prev_str * cnt
        return stack[0][0]

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(1)******

递归

beats 100%

class Solution:
    def decodeString(self, s):
        """
        :type s: str
        :rtype: str
        """
        if not s or len(s) == 0:
            return ''       
                    
        def helper(s):
            res = ''
            open_idx = s.find('[')
            if open_idx != -1: 
                open_cnt = 1
                idx = open_idx + 1
                while idx < len(s) and open_cnt > 0: # 找到与第一个 '[' 匹配的 ']'
                    if s[idx] == '[':
                        open_cnt += 1
                    elif s[idx] == ']':
                        open_cnt -= 1
                    idx += 1
                close_idx = idx - 1
                tmp_str = ''
                cnt, i = 0, 0
                while i < open_idx and not s[i].isdigit(): # 找到数字前可能有的字符串，见test case2
                    tmp_str += s[i]
                    i += 1
                cnt = int(s[i:open_idx])
                return tmp_str + cnt * helper(s[open_idx+1:close_idx]) + helper(s[close_idx+1:])
            else:
                return s
            
        return helper(s)