DAY 11
0
Software Development

## Day.11 Decode String

Leetcode #394. Decode String

ex.
Input: s = "3[a]2[bc]"
Output: "aaabcbc"

Input: s = "3[a2[c]]"
Output: "accaccacc"

Input: s = "3[a2[c]]"
Output: "accaccacc"

ex. 3[a2[cq]]

stack: 3 [ a 2 [ c q

``````num: 2
str: cq
stack: 3 [ a
``````

``````stack: 3 [ a cqcq
``````

``````num: 3
str: acqcq
stack:
``````

``````// 昨天寫的stack
type Stack struct {
nodes []string
}

func (s *Stack) Push(val string) {
s.nodes = append(s.nodes, val)
}

func (s *Stack) Pop() string {
if len(s.nodes) == 0 {
return ""
}

res := s.nodes[len(s.nodes)-1]
s.nodes = s.nodes[0 : len(s.nodes)-1]

return res
}
``````
``````func decodeString(s string) string {
stack := Stack{}
for _, v := range s {
// 遇到']'之前 都直接往stack推
if v != ']' {
stack.Push(string(v))
continue
}

// 遇到']'了
str := ""
index := len(stack.nodes) - 1
for index >= 0 {
// 找到'['跳出迴圈
if stack.nodes[index] == "[" {
stack.Pop() // 把'['拿掉
index--
break
}

str = string(stack.Pop()) + str
index--
}

// 處理數字
num := ""
for index >= 0 {
_, err := strconv.Atoi(stack.nodes[index])
if err != nil {
// 不是數字了 跳出迴圈
break
}

num = stack.Pop() + num
index--
}

count, _ := strconv.Atoi(num)
stack.Push(strings.Repeat(str, count))
}

return strings.Join(stack.nodes, "")
}
``````

leetcode 執行結果

``````Runtime: 0 ms, faster than 100.00% of Go online submissions for Decode String.
Memory Usage: 2 MB, less than 71.33% of Go online submissions for Decode String.
``````