JAVAプログラミング:文字列復号(LeetCode:394)
1312 ワード
符号化された文字列を指定し、復号された文字列を返します.
符号化規則は、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を返す.
構想:行ってから遍歴して、数字に出会ったら覚えて、アルファベットに出会って直接現在の答えに加えて、左かっこに出会って、再帰的にサブストリングの答えを解いて、右かっこに出会って直接答えに戻って、事前に各左かっこに対応する右かっこがどこにあるかを処理して、このようにあなたに1回の文字列だけを遍歴させることができます!
符号化規則は、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を返す.
構想:行ってから遍歴して、数字に出会ったら覚えて、アルファベットに出会って直接現在の答えに加えて、左かっこに出会って、再帰的にサブストリングの答えを解いて、右かっこに出会って直接答えに戻って、事前に各左かっこに対応する右かっこがどこにあるかを処理して、このようにあなたに1回の文字列だけを遍歴させることができます!
class Solution {
public String decodeString(String s) {
int sum,p=0,num=0;
int[] pre=new int[s.length()];
int[] prere=new int[s.length()];
for(int i=0;i='0' && s.charAt(i)<='9') {
sum=sum*10+(s.charAt(i)-'0');
continue;
}
if(s.charAt(i)=='[') {
str.append(decodeString(s.substring(i+1)));
for(int j=0;j