Проблема в создании строкового алгоритма

Question

Для заданной строки, состоящей только из 'a' и 'b', разрешенная операция заключается в удалении подстроки "abb", если она присутствует, из строки. У меня вопрос после применения этой операции в любое время я могу сделать строку пустой. Мне нужен алгоритм O(n).

Пример, abbabb-> да

aabbbb-> да, так как aabbbb-> abb-> пусто

aaabbb-> нет, так как aaabbb-> aab

Все, что я могу придумать, - это алгоритм O(n^2), в котором я успешно нахожу положение подстроки, используя substr() или find(), и затем удаляю ее, пока строка не станет пустой или не найдет "abb" в Это.

Answer 1

Вот пример того, что я предложил в комментарии:

for i = 0 to word.length-1
    if word[i] == 'b'
        if stack.empty() //no corresponding a
            return false
        if stack.top() == 'a' //first b after an a
            stack.push('b')
        else                  //second b after an a
            stack.pop()       //pop last two letters
            stack.pop()
    else
        stack.push('a')
return stack.empty()

Могут быть некоторые граничные условия, которые необходимо проверить, и, конечно же, в любой точке pop() вы не сможете вернуть false. Кажется, работает на возможные входные данные, которые происходят со мной.

Я думаю, что необходимо математически обосновать ту часть, в которой я прокомментировал "второй b после a". С предположением, что стек был пуст в начале, если я ничего не пропустил, то точка выглядит правильно.

Answer 2

Нет необходимости хранить что-либо, кроме количества неиспользованных пар b в конце строки, как вы читаете справа налево. (И это решается чтением ввода только один раз, так что O(n) время O(1) пространство) Это очень напоминает поиск дискретных конечных автоматов для обычного языка. Если вы видите два б, увеличьте count, Если вы видите один b, добавьте половину пары (обновите логическую переменную и, возможно, увеличьте счетчик). Если вы видите a и у вас нет пары b, потерпите неудачу, иначе count--, Если вы достигли конца строки и не было никаких дополнительных символов b, строка была действительной.

Answer 3

Используйте два счетчика, чтобы избежать использования стека. Вот реализация C++, надеюсь, это работает.

bool canBeDone(string s)
{
int aCount = 0;
int bCount = 0;
for(int i=0;i<s.length();++i)
{
    if(s[i] == 'a')
    {
        aCount++;
        continue;
    }
    if(s[i] == 'b' && aCount == 0)
        return false;
    else
    {
        bCount += 1;
        if(bCount == 2)
        {
            bCount = 0;
            aCount--;
        }
    }
}
if(!aCount && !bCount)return true;
return false;
}

Answer 4

Очень простая и понятная реализация в Erlang O(n) пространство и время (к сожалению, даже алгоритм clwhisk нуждается в O(n) пространство в Эрланге из-за lists:reverse/1):

-module(abb).

-export([check/1, clwhisk/1, test/0]).

check(L) when is_list(L) ->
    check(L, []).

check(L, "bba" ++ T) -> check(L, T);
check([H|T], S) -> check(T, [H|S]);
check([], S) -> S =:= [].

clwhisk(L) when is_list(L) ->
    clwhisk(lists:reverse(L), 0).

clwhisk([$b|T], C) -> clwhisk(T, C+1);
clwhisk([$a|T], C) -> C >= 2 andalso clwhisk(T, C-2);
clwhisk(L, C) -> L =:= [] andalso C =:= 0.

test() ->
    true = abb:check("abbabb"),
    true = abb:check("aabbbb"),
    false = abb:check("aaabbb"),
    true = abb:check("ababbb"),
    true = abb:clwhisk("abbabb"),
    true = abb:clwhisk("aabbbb"),
    false = abb:clwhisk("aaabbb"),
    true = abb:clwhisk("ababbb"),
    ok.

И есть C реализация алгоритма clwhisk качестве фильтра:

#include <stdlib.h>
#include <stdio.h>

static inline const char *last(const char* s){
    for(;*s && *s!='\n';s++);
    return s-1;
}

static int check(const char* s){
    int count=0;
    const char *ptr = last(s);
    for(; ptr >= s; ptr--)
        if(*ptr == 'b') {
            count++;
        }
        else if(*ptr == 'a') {
            count -= 2;
            if(count < 0)
                return 0;
        }
        else return 0;
    return count == 0;
}

int main(void) {
    char *line = NULL;
    size_t len = 0;
    while( getline(&line, &len, stdin) != -1 )
        if(*line && *line != '\n' && check(line))
            fputs(line, stdout);
    return EXIT_SUCCESS;
}