LeetCode 394 Decode String

LeetCode

Given an encoded string, return its 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].

Example 1:

Input: s = “3[a]2[bc]”
Output: “aaabcbc”

Example 2:

Input: s = “3[a2[c]]”
Output: “accaccacc”

Example 3:

Input: s = “2[abc]3[cd]ef”
Output: “abcabccdcdcdef”

Example 4:

Input: s = “abc3[cd]xyz”
Output: “abccdcdcdxyz”

Constraints:

1 <= s.length <= 30 s consists of lowercase English letters, digits, and square brackets '[]'.
s is guaranteed to be a valid input. All the integers in s are in the range [1, 300].

题目大意：

将循环体表示展开

Stack解题思路(推荐)：

见到括号就考虑用Stack，此题有字符和数字，所以考虑用两个Stack

解题步骤：

运用模板

注意事项：

1. 同级为括号外（包括括号以左，以右），但数字和字符分别存于两个stack。括号内为另一级，入栈。

Python代码：

def decodeString(self, s: str) -> str:
	res, num, stack_num, stack_str = '', 0, [], []
	for char in s:
		if char.isdigit():
			num = num * 10 + int(char)
		if char.isalpha():
			res += char
		if char == '[':
			stack_num.append(num) # [3]
			stack_str.append(res) # 2c
			num = 0
			res = ''
		if char == ']':
			tmp = stack_str.pop() # '2c'
			n = stack_num.pop() # 3
			res = tmp + n * res # 2c + 3*d=ccddd
	return res

算法分析：

时间复杂度为O(n)，空间复杂度O(n)

---

递归算法II解题思路(不推荐)：

用index作为全局变量，扫每一个字符，类似于Leetcode 297。
遇到字符append到result，遇到数字记录次数k，遇到左括号就递归decodeString(s), 递归返回decodedString, 跳过右括号，result.append(decodedString) k次，最后返回result。

如3[a2[c]]

伪代码：

decodeString('3[a2[c]]')
    k = 3  
    acc = decodeString('a2[c]')
         result = a
         k = 2
         'c'  = decodeString('c')
         result = acc
   result = accaccacc