Decode String - LeetCode

給一個加密過的string，回傳解密後的string

加密規則：k[encoded_string] ，k代表括號裡面的string要重複幾次

數字只用作k，不會用作encoded_string

Example:

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

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

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

初始化一個stack

for loop 走訪 s (for l in s)

• if l == ]
  • var string
  • while stack top ≠ [
    • top = stack.pop
    • string = top + string
  • stack.pop // remove [
  • var k
  • while (stack is not empty) && (stack top ≠ number)
    • top = stack.pop
    • k = top + k
  • newString = toNumber(k) * string
  • stack.push(newString)
• else
  • stack.push(l)

result = stack to string

return result

package main

import (
	"fmt"
	"strconv"
)

func main() {
	fmt.Println(decodeString("2[abc]3[cd]ef"))
}

// 2022/10/9 stack solution
func decodeString(s string) string {
	stack := []string{}

	for _, l := range s {

		current := string(l)

		if current == "]" {
			tmp := ""
			for len(stack) > 0 && stack[len(stack)-1] != "[" {
				top := stack[len(stack)-1]
				stack = stack[:len(stack)-1] // pop
				tmp = top + tmp

			}

			stack = stack[:len(stack)-1] // pop [

			k := ""
			for len(stack) > 0 && IsNumber(stack[len(stack)-1]) {
				top := stack[len(stack)-1]
				stack = stack[:len(stack)-1] // pop
				k = top + k
			}

			intK, _ := strconv.Atoi(k)

			newString := ""
			for i := 0; i < intK; i++ {
				newString += tmp
			}

			stack = append(stack, newString)

		} else {
			stack = append(stack, current)
		}

	}
	result := ""

	for i := 0; i < len(stack); i++ {
		result += stack[i]
	}

	return result

}

func IsNumber(s string) bool {
	for _, r := range s {
		if r < '0' || r > '9' {
			return false
		}
	}
	return true
}