LeetCode 394. 文字列復号

1818 ワード

タイトルの説明


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

もんだいぶんせき


遍歴文字列は、数に遭遇した場合numに数を格納する.左括弧に遭遇した場合、numを数スタックに押し込み、左括弧の前の文字列ansを文字列スタックに押し込み、numを0にクリアし、ansも空にします.右かっこに遭遇した場合、数スタックのスタックトップ数をkとしてポップアップし、現在のansをk回繰り返し、文字列スタックのスタックトップ文字列の後ろに接続し、文字列スタックのスタックトップ文字列をポップアップし、ansとして保存します.アルファベットに遭遇した場合は、ansをアルファベットに接続します.文字列ループが終了すると、結果ansが返されます.

コード実装

class Solution {
public:
    string decodeString(string s) {
        string ans = "";
        stack snum;
        stack sstr;
        int num = 0;
        for(int i = 0; i < s.size(); i++){
            while(s[i] >= '0' && s[i] <= '9'){
                num = num * 10 + (s[i] - '0');
                i++;
            }
            if(s[i] == '['){
                snum.push(num);
                sstr.push(ans);
                num = 0;
                ans = "";
            }
            else if(s[i] == ']'){
                int k = snum.top();
                snum.pop();
                for(int i = 0; i < k; i++){
                    sstr.top() += ans;
                }
                ans = sstr.top();
                sstr.pop();
            }
            else{
                ans += s[i];
            }
        }
        return ans;
    }
};