アルゴリズム-スナップ[394]文字列復号

スナップ[394]文字列復号
タイトル
符号化された文字列を指定し、復号された文字列を返します.符号化規則は、k[encoded_string]であり、カッコ内のencoded_を表すstringはちょうどk回繰り返します.注意kは正の整数であることを保証する.入力文字列は常に有効であると考えられます.入力文字列には余分なスペースがなく、入力した四角カッコは常にフォーマットの要件を満たしています.また、元のデータには数字は含まれておらず、すべての数字は重複回数kのみを表し、例えば3 aや2[4]のような入力は現れないと考えられます.
例:

s = "3[a]2[bc]",    "aaabcbc".
s = "3[a2[c]]",    "accaccacc".
s = "2[abc]3[cd]ef",    "abcabccdcdcdef".

問題解一:補助スタック
ぶんせき
2つの補助スタックが構築され、1つのスタックstack_resが一時的な結果を格納し、1つのスタックstack_mulが倍数を格納し、文字列sの文字cを巡回する.

cが数字である場合、数字文字をmulに変換し、乗数として記録する.

cがアルファベットである場合、結果文字列resの末尾にアルファベット文字を追加する.

cが[である場合、スタックに入る操作を行い、mulとresをそれぞれスタックstack_mulとスタックstack_resに押し込み、乗数mulと結果配列resをそれぞれ0と空にする.

乗数mulは、一時的にスタックを出たときの一時結果resの倍数を記録するために使用される.

の一時結果resは、[...]の間の文字列を記録した.すなわち、1対の[]を1層と見なすと、resは現在の層の文字列を記録した.

cが]である場合、スタックを出る操作が行われ、スタックstack_mulおよびスタックstack_resのそれぞれから、last_resおよびcur_mulの要素がポップアップされ、次いで、文字列res = last_res + cur_mul * resがつづられる.

last_resは、前の[から本層[までの文字列、すなわち、前の層の文字列(本層を含まない)を記録する.

乗数cur_mul、すなわちスタックstack_mulがポップアップされたばかりの要素は、現在のレイヤ内の文字列の重複の倍数を計算するために使用される.

コード実装

class Solution {
     
    public String decodeString(String s) {
     
        int mul = 0;
        StringBuilder res = new StringBuilder();
        LinkedList<Integer> stack_mul = new LinkedList<>();
        LinkedList<String> string_mul = new LinkedList<>();
        for (Character c : s.toCharArray()) {
     
            if (c == '[') {
     
                stack_mul.addLast(mul);
                string_mul.addLast(res.toString());
                mul = 0;
                res = new StringBuilder();
            } else if (c == ']') {
     
                int cur_mul = stack_mul.removeLast();
                String last_res = string_mul.removeLast();
                StringBuilder tmp = new StringBuilder();
                for (int i = 0; i < cur_mul; i++) {
     
                    tmp.append(res);
                }
                res = new StringBuilder(last_res + tmp);
            } else if (c >= '0' && c <= '9') {
     
                //       1    ，        34      
                mul = mul * 10 + Integer.parseInt(c + "");
            } else {
     
                res.append(c);
            }
        }
        return res.toString();
    }
}

複雑度分析
時間複雑度:sを1回だけ巡回する必要があるので,複雑度はO(n)である.
空間複雑度:最悪の場合、[]を除くすべての文字がスタックに入るため、空間複雑度は最悪O(n)である.