好串

链接

这题我在洛谷(3215)看过类似的

a和b是成对出现的,且a在b前面

比如在aabb的aa之间插入一对ab,得到aababb,我们只要删去ab,就得到aabb,再删去ab

就得到ab,再删就是空字符串了,那么显然

只要按照这种方法删去最后得到的是空字符串的,我们称之为好串

我们在代码中实现肯定是要循环的,怎么实现呢

采用回溯法(应该)

比如

s=aabb

i=1

s[1]=a且s[2]=b我们就删去,

然后我们把索引退回去,即i--;

要是i一开始为0的话会越界,所以我们要写好条件判断,

而且,由于删去元素后,字符串长度会变少,我们得注意越界问题

代码实现

#include<iostream>
#include<string>
using namespace std;
int main() {
    string input;
    cin >> input;
    int n = input.size();
        for (int j = 0;j < n- 1;) {
            
            if (input[j] == 'a' && input[j + 1] == 'b') {
                input.erase(j, 2);
                n = input.size();
                if (j > 0) j--;
            }
            else j++;
           
        }
    if (input.empty()) {
        cout << "Good";
    }
    else {
        cout << "Bad";
       
    }
}

时间复杂度:O(n²) 空间复杂度:O(n)