394.文字列復号(中程度の問題)
9029 ワード
タイトルの説明:符号化された文字列を指定し、復号された文字列を返します.
符号化規則は、k[encoded_string]であり、カッコ内のencoded_を表すstringはちょうどk回繰り返します.注意kは正の整数であることを保証する.
入力文字列は常に有効であると考えられます.入力文字列には余分なスペースがなく、入力した四角カッコは常にフォーマットの要件を満たしています.
また、元のデータには数字は含まれておらず、すべての数字は重複回数kのみを表し、例えば3 aや2[4]のような入力は現れないと考えられます.
例:
s="3[a]2[bc],"aaabcbc"を返す.s="3[a 2[c]",は"accaccacc"を返す.s="2[abc]3[cd]ef"、abcabccdcdefを返す.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/decode-string著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.解法:
符号化規則は、k[encoded_string]であり、カッコ内のencoded_を表すstringはちょうどk回繰り返します.注意kは正の整数であることを保証する.
入力文字列は常に有効であると考えられます.入力文字列には余分なスペースがなく、入力した四角カッコは常にフォーマットの要件を満たしています.
また、元のデータには数字は含まれておらず、すべての数字は重複回数kのみを表し、例えば3 aや2[4]のような入力は現れないと考えられます.
例:
s="3[a]2[bc],"aaabcbc"を返す.s="3[a 2[c]",は"accaccacc"を返す.s="2[abc]3[cd]ef"、abcabccdcdefを返す.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/decode-string著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.解法:
class Solution {
public String decodeString(String s) {
StringBuilder sb = new StringBuilder();
Stack<Integer> st_time = new Stack<>();
Stack<String> st_res = new Stack<>();
char[] ch = s.toCharArray();
int times = 0;
for (int i = 0; i < ch.length; i++) {
if(ch[i] - '0' >= 0 && ch[i] - '9'<= 0){
times = times*10 + ch[i] - '0';
}
else if(ch[i] == '['){
// , sb ,
st_time.push(times);
st_res.push(sb.toString());
times = 0;
sb = new StringBuilder();
}
else if(ch[i] == ']'){
// , sb
StringBuilder temp = new StringBuilder();
int cur_time = st_time.pop();
for (int j = 0; j < cur_time; j++) {
temp.append(sb);
}
sb = new StringBuilder(st_res.pop()+temp);
}
else {
sb.append(ch[i]);
}
}
return sb.toString();
}
}