leetcode菜狗入門|394.文字列復号

13528 ワード

文字列復号


タイトルの説明


符号化された文字列を指定し、復号された文字列を返します.
符号化規則は、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つのデジタルスタック、1つの文字スタック、デジタルスタックの格納倍数を作成します.文字スタックが「」に遭遇すると、「[」に遭遇するまでスタックを出て、デジタルスタックはスタックを突き出して、スタックの文字列を倍数で変換して、文字スタックが空でない場合は文字スタックに入れて、さもなくばansの後でつなぎ合わせて、文字スタックとデジタルスタックがすべて空である場合、現在の文字を直接ansの後でつなぎ合わせます

コード#コード#

class Solution {
public:
    string decodeString(string s) {
        stack<int> count;
        stack<char> str;
        string ans = "";
        if(s.length() == 0) return ans;
        int i = 0;
        int num = -1;
        while(i < s.length()){
            while(s[i] >= '0' && s[i] <= '9' && i < s.length()){
                if(num == -1)
                    num = s[i] - '0';
                else
                    num = num*10 + (s[i]-'0');
                i++;
            }
            if(num != -1){
                count.push(num);
                num = -1;
            }
            if(count.empty() && str.empty()){
                ans.push_back(s[i]);
                i++;
                continue;
            }
            if(s[i] != ']'){
                str.push(s[i]);
                i++;
            }
            else{
                string temp = "";
                while(str.top() != '['){
                    temp.push_back(str.top());
                    str.pop();
                }
                str.pop();
                reverse(temp.begin(), temp.end());
                int beishu = count.top();
                //cout<
                count.pop();
                string cur = temp;
                for(int j = 1; j <beishu; j++){
                    temp += cur;
                }
                if(str.empty())
                    ans += temp;
                else{
                    for(int j = 0; j < temp.length(); j++){
                        str.push(temp[j]);
                    }
                }
                i++;
            }
        }
        return ans;
    }
};