基于指定生成规则的字符串有效性验证及更优算法咨询

首先明确你给出的四条生成规则对应的合法字符串本质：所有合法串均可拆分为若干个互不重叠的偶长度回文子串，单个偶长度回文子串满足：任意嵌套的首尾相同字符对，最内层一定是两个连续相同字符。

最优解法：栈实现O(n)时间复杂度 #

你之前的O(n²)方案不是最优选择，存在更简单的线性时间解法，核心思路用栈匹配字符对：

• 初始化一个空栈
• 遍历输入字符串的每一个字符：
  • 如果栈不为空，且当前字符与栈顶元素相等，直接弹出栈顶元素
  • 否则将当前字符压入栈中
• 遍历结束后，若栈为空则返回True，否则返回False

解法原理 #

这个逻辑刚好完全匹配你的生成规则：

1. 规则2生成的成对相同字符，入栈第一个后，第二个直接弹出，不会留在栈中
2. 规则3首尾加相同字符的嵌套场景，外层字符会先入栈，等内层所有字符都匹配弹出后，最后和另一侧的相同字符匹配弹出
3. 规则4的多合法串拼接场景，前一个合法串全部匹配弹出后栈会清空，后续的字符串相当于重新走匹配逻辑，互不干扰

测试示例验证 #

1. 输入aa：压入a，第二个a匹配弹出，栈空返回True
2. 输入baab：依次压入b、a，第三个字符a匹配弹出栈顶a，第四个字符b匹配弹出栈顶b，栈空返回True
3. 输入edggdefeeddeef：遍历过程中所有字符依次成对匹配弹出，最终栈空返回True
4. 反例输入abab：所有字符依次入栈无匹配，最终栈非空返回False

补充说明 #

你之前尝试的计数法之所以失效，是因为只统计了字符出现次数，没有考虑顺序，而栈方案刚好同时兼顾了字符出现的顺序和次数要求，空间复杂度最坏为O(n)，绝大多数场景下已经是最优选择。

内容的提问来源于stack exchange，提问作者MHL