[C++]プログラマ-ペアリングの削除


問題の説明
ペアリングを削除するには、アルファベット小文字の文字列で開始します.まず、文字列内で同じ文字を2つ持つペアを検索します.次に、この2つの文字列を削除し、前後に文字列を接続します.この手順を繰り返してすべての文字列を削除すると、ペアリングの削除が終了します.文字列Sが指定されている場合は、ペアリングを正常に削除できるかどうかを返す戻り関数を完了します.成功した場合は1を返し、そうでない場合は0を返します.
例えば、文字列S=Baabaa
b aa baa → bb aa → aa →
すべての文字列を中の順序で削除できるため、1を返します.
せいげんじょうけん
文字列の長さ:100,000未満の自然数
すべての文字列は小文字で構成されています.
解法
初めて見たときは、再帰的に実現すべきだと思っていましたが、ペアリングすれば、外し続けるべきだと思いました...制限事項では、文字列の長さが1000000の範囲内であるため、効率の問題が発生する可能性があります.
そして考えてみると、スタックを利用して文字を入力しながらペアリングすれば、popでO(n)の時間的複雑さを解決できると思います.
そこで,以下のアルゴリズムを記述した.
  • Sの各要素をスタックに順次プッシュします.
  • を合わせると、すぐに流行します.
  • ペアが建設されていなければ、推進を続けます.
  • 最後の要素にプッシュすると、スタックは空ではなく失敗し、空はに成功します.
    2つの同じ文字がくっついている場合にのみ削除できるので、上記の方法は全く問題ありません.
    ソースコード
    #include <bits/stdc++.h>
    
    using namespace std;
    
    int solution(string s)
    {
        int answer = 0;
    
        stack <char> stack;
    
        for(int i = 0; i < s.length(); i++)
        {
            if(stack.empty() || stack.top() != s[i])
                stack.push(s[i]);
            else if(stack.top() == s[i])
                stack.pop();
        }
    
        if(stack.empty())
            answer = 1;
    
        return answer;
    }
    
    
    フィードバック
    しばらくはベクトル資料構造のみを用いているため,他の資料構造に対する感覚が不足している.