使字符串变得漂亮或丑陋的算法

Question

我很难找到解决以下难题的算法-如果一个字符串连续有 3 个元音字母，或连续有 5 个辅音字母，或两者都有，则该字符串被称为丑陋的。如果一个字符串不丑陋，它就被称为 nice。给你一个字符串 s，由大写字母('A'-'Z')和问号('?')组成。你能找到一种算法来判断字符串是否可以通过用字母替换问号来变得更好吗？

示例 -

1. “EE?FFFF” - 无法变得友善。插入辅音或元音会使它变得难看。

2. “H??LOWOR??” - 可以做得很好。

P.S - 不是家庭作业，而是互联网上编程难题的一部分。

Answer 1

请注意，唯一可能丑陋的字符串是那些由于给定字母而已经丑陋的字符串或仅包含单例问号的字符串。这是证明的草图:

• 对于任何一组两个问号，让左边的问号与左边的问号相反，让右边的问号与右边的问号相反。例如。 V??C 应该变成VCVC。如果字符串本来就不丑的话，这样的替换永远不会使它变得丑陋。
• 对于任何一组三个或更多的问号，如上设置最左边和最右边的问号，然后交替使用 V 和 C 之间的中间问号。这可能会导致引入两个连续的 V 或 C，但绝不会引入三个。

因此，我们只剩下两个简单的案例。

• 检查一个字符串是否已经丑陋是一个简单的正则表达式。
• 如果问号的一侧有两个元音字母而另一侧有四个辅音字母，那么单例会使字符串变丑的唯一情况；但你不能只检查那些，因为替换可能会引入这样的模式(考虑 EE？FFF？EE)。但在这一点上，您可以通过从左到右工作来检查，通过插入右邻居的反义词来解决每个单例问号，除非这会使字符串变丑，如果存在两个元音/四个辅音模式则停止。<