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
}
|