Leetcode punch in

leetcode The first day of punch in

A very simple string deletion problem , Hit multiple pits

Give a string of lowercase letters  S, Duplicate deletion selects two adjacent and identical letters , And delete them . stay S Repeat the delete operation on , Until you can't delete . Returns the final string... After all the duplicates have been deleted . The answer is guaranteed to be unique .

Example :

Input :abbaca

Output :ca

To understand and run is to first "bb" Delete , Get a string "aaca", Then judge and delete the adjacent "aa", obtain "ca", because "ca' Adjacent characters do not have the same , So that's the final result .

Programming and commissioning problems

(1)  The first is the circulation problem , Only one cycle was judged , The strings obtained by deleting the original adjacent characters are not integrated , Then it is determined again whether there are adjacent characters .

(2)  After considering the above problem ,"aaaaaa" The last two of the string "aa" But it's ignored , Or the loop setting is wrong .

Generally speaking, facing this deletion problem , The length of the string changes every time , You need to set up two auxiliary spaces , One is defined as the length of the string before it has not been changed , One is set to the length after change , Then set the cycle condition , If the two lengths are not equal, it means that the final result has not been obtained .

class Solution {
public:
    string removeDuplicates(string S) {
        int now=S.length();
        int next=1;
        while(now!=next)// The current string length is not equal to the length after the next removal 
        {
            now=S.length();
            for(int i=0;i<now;i++){
                if(S[i]==S[i+1])S.erase(i,2);

            }
            next=S.length();
        }
        return S;

    }
};

leetcode The first logic of problem brushing , When the logic is clear, we can solve the problem , Otherwise, there will be a lot of bug.