使String变得漂亮或丑陋的算法

Question

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

示例 -

1. "EE？FFFF" - 不能做得很好.插入辅音或元音会使它变得难看.

2. "H 24 LOWOR ??" - 可以做得很好.

PS - 不是家庭作业,而是互联网上编程难题的一部分.

Answer 1

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

• 对于任何一组两个问号,使左侧问号与左侧邻居相反,右侧问号与右侧邻居相反.例如V ?? C应该成为VCVC.如果它不是丑陋的话,这样的替换永远不会变成难看的字符串.
• 对于任何三个或更多个问号的集合,设置最左边和最右边的问号,然后在V和C之间交替使用中间问号.这可能会导致引入两个连续的V或C,但不会引入三个.

所以,我们留下了两个简单的案例.

• 检查一个字符串是否已经丑陋是一个简单的正则表达式.
• 如果问号的一侧有两个元音而另一侧有四个辅音,那么单身可以使一个字符串变得难看的唯一情况就是如此; 但你不能只检查那些,因为替换可能会引入这样的模式(考虑EE？FFF？EE).但此时,您可以通过从左到右进行检查,通过插入右邻居的相反方法来解决每个单例问号,除非这会使字符串变得难看并且如果存在两个元音/四个辅音模式则停止.

Answer 2

Haskell中的解决方案:

import System (getArgs)

nicePart :: Int -> Int -> String -> Bool
nicePart 3 _ _  = False
nicePart _ 5 _  = False
nicePart _ _ "" = True
nicePart v c ('?':as) = nicePart (v+1) 0 as || nicePart 0 (c+1) as
nicePart v c (a:as)
   | a `elem` "AEIOU" = nicePart (v+1) 0 as
   | otherwise        = nicePart 0 (c+1) as

nice :: String -> Bool
nice as = nicePart 0 0 as

main = getArgs >>= print . nice . unwords

该函数保持在当前点看到的连续元音和辅音的数量.如果有太多它返回False.如果找到问号,则进行两次递归调用,一次将问号计为元音,一次作为辅音,检查这些变化是否合适.