1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// @Title: 字符串解码 (Decode String)
// @Author: 15816537946@163.com
// @Date: 2019-10-13 13:32:45
// @Runtime: 0 ms
// @Memory: 2.1 MB
import "strconv"

/*
 * @lc app=leetcode.cn id=394 lang=golang
 *
 * [394] 字符串解码
 *
 * https://leetcode-cn.com/problems/decode-string/description/
 *
 * algorithms
 * Medium (46.08%)
 * Likes:    120
 * Dislikes: 0
 * Total Accepted:    7.6K
 * Total Submissions: 16.4K
 * Testcase Example:  '"3[a]2[bc]"'
 *
 * 给定一个经过编码的字符串,返回它解码后的字符串。
 *
 * 编码规则为: k[encoded_string],表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
 *
 * 你可以认为输入字符串总是有效的;输入字符串中没有额外的空格,且输入的方括号总是符合格式要求的。
 *
 * 此外,你可以认为原始数据不包含数字,所有的数字只表示重复的次数 k ,例如不会出现像 3a 或 2[4] 的输入。
 *
 * 示例:
 *
 *
 * s = "3[a]2[bc]", 返回 "aaabcbc".
 * s = "3[a2[c]]", 返回 "accaccacc".
 * s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
 *
 *
 */

func decodeString(s string) string {
	n := len(s)

	// i是第一个数字的位置
	i := 0
	for i < n && (s[i] < '0' || s[i] > '9') {
		i++
	}
	if i == n {
		// 没有数字, 直接返回s
		return s
	}

	// j是第一个'['的位置
	j := i + 1
	for s[j] != '[' {
		j++
	}

	// k 是与j对应的'['的']'的位置
	k := j
	count := 1
	for count > 0 {
		k++

		if s[k] == '[' {
			count++
		} else if s[k] == ']' {
			count--
		}
	}

	//      i:第一个数字的位置
	//      |  j:第一个 '[' 的位置
	//      |  |       k:与 j 的 '[' 对应的 ']' 的位置
	//      ↓  ↓       ↓
	// "abcd234[*******]efg"

	num, _ := strconv.Atoi(s[i:j])

	// return s[:i] + times(num, decodeString(s[j+1:k])) + decodeString(s[k+1:])
	return s[:i] + times(num, decodeString(s[j+1:k])) + decodeString(s[k+1:])
}

func times(n int, s string) string {
	res := ""
	for i := 0; i < n; i++ {
		res += s
	}
	return res
}