根据Rules验证字符串

Question

字符串是使用规则形成的，我们需要验证它。

输出:返回True或False

1. 以空字符串" "开头
2. 取任意字符并将其命名为一对" aa "
3. 取任意字符并在末尾添加字符" baab "
4. 连接使用上述方法形成的任何字符串

输入:aa输出:真正的

输入:baab输出:真正的

输入:edggdefeeddeef输出:真正的

我试图使用计数方法(就像您使用所有字符的布尔数组来递增和递减计数，当计数为0时，您创建其余的子字符串)，以O(n)中的问题，但项目的顺序很重要，所以它不起作用。

我认为唯一的方法是使用左和右指针，并保持从左计数，当你达到总计数为0检查如果它是一个回文，然后移动窗口。复杂度将是O(n^2)，你形成窗口，然后检查它是否为回文。

我在这里错过了什么吗?有更好的解决方案吗?

Answer 1

你的描述听起来像是你想要识别的语言的语法是

S -> eps | A S A S
A -> a | b | c | ...

在单词中，这是所有字符串，其中字母对只包含字母对(或什么都不包含)。

这导致了一个很好的递归形式。当我在输入中看到字符c时，我开始匹配该c。如果输入的下一个字符是c，很好。我完成了。否则，我将递归地匹配下一个字符，然后再次尝试将c与剩下的字符匹配。

在C中，它看起来像

#include <stdio.h>
#include <stdbool.h>
static bool match(int c) {
int next = getchar();
if (next == EOF || next == 'n') return false;
if (next == c) return true;
return match(next) && match(c);
}
static bool check(void) {
int c = getchar();
if (c == EOF || c == 'n') return true;
return match(c) && check();
}
int main(void) {
bool result = check();
printf("Result: %sn", result ? "yes" : "no");
return 0;
}

我很确定这是正确的。

$ echo edggdefeeddeef | ./foo
Result: yes
$ echo edggdefeedeef | ./foo
Result: no