文章作者：Tyan
博客：noahsnail.com ?|? CSDN ?|? 簡(jiǎn)書
1. 問(wèn)題描述
Given an encoded string, return it's 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; 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 won't be input like 3a or 2[4].
Examples:
s = "3[a]2[bc]", return "aaabcbc".
s = "3[a2[c]]", return "accaccacc".
s = "2[abc]3[cd]ef", return "abcabccdcdcdef".
中文
給定一個(gè)經(jīng)過(guò)編碼的字符串柒瓣，返回其解碼字符串。編碼規(guī)則為：k[encoded_string]，其中中括號(hào)內(nèi)的encoded_string被重復(fù)k次。注意k一定是正整數(shù)。
2. 求解
本題中明顯有括號(hào)的匹配問(wèn)題霸妹，因此需要使用棧來(lái)求解瞻赶。當(dāng)碰到右括號(hào)（]）時(shí)维雇，字符串出棧赊舶，碰到左括號(hào)（[）時(shí)，保存左右括號(hào)內(nèi)的字符串（[]）赶诊，繼續(xù)出棧笼平，保存字符串重復(fù)次數(shù)，直至棧為空或碰到非數(shù)字舔痪。要注意重復(fù)次數(shù)不是個(gè)位數(shù)寓调，將字符串重復(fù)之后壓入棧中。繼續(xù)處理剩余字符串锄码，同樣執(zhí)行上述過(guò)程夺英，直至處理完字符串晌涕。然后將棧中所有的字符出棧構(gòu)成結(jié)果字符串返回。
public class Solution {
public String decodeString(String s) {
int n = s.length();
Stack<Character> stack = new Stack<Character>();
String result = "";
String temp = "";
for (int i = 0; i < n; i ++) {
char str = s.charAt(i);
if (str != ']') {
stack.push(str);
} else {
char ch = stack.pop();
while (ch != '[') {
temp = ch + temp;
ch = stack.pop();
}
//字符串重復(fù)次數(shù)
String times = "";
while(!stack.isEmpty()) {
ch = stack.pop();
if(Character.isDigit(ch)) {
times = ch + times;
}else {
stack.push(ch);
break;
}
}
//重復(fù)字符串痛悯，壓入棧中
for(int j = 0; j < Integer.parseInt(times); j++) {
for(int k = 0; k < temp.length(); k++) {
stack.push(temp.charAt(k));
}
}
temp = "";
}
}
while(!stack.isEmpty()) {
result = stack.pop() + result;
}
return result;
}
}
