394. Decode String ⭐
Medium
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; there are 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 will not be input like 3a
or 2[4]
.The test cases are generated so that the length of the output will never exceed
105
.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"
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]
.
func decodeString(s string) string {
return helper(s)
}
func helper(s string) string {
res := ""
for i := 0; i < len(s); i++ {
if s[i] >= '0' && s[i] < '9' {
endNumber := strings.Index(s[i:], "[") + i
repeatCount, _ := strconv.Atoi(s[i:endNumber])
start := endNumber + 1
i = findScopeEndingBracket(start, s)
tmp := helper(s[start:i])
res += strings.Repeat(tmp, repeatCount)
} else {
res += string(s[i])
}
}
return res
}
func findScopeEndingBracket(i int, s string) int {
bracketsCount := 1
for i < len(s) && bracketsCount > 0 {
if s[i] == '[' {
bracketsCount++
} else if s[i] == ']' {
bracketsCount--
}
i++
}
return i - 1
}
Last modified 6mo ago