模式匹配:将字符串与模式匹配

Question

我试着在字符串中匹配一个模式。我想不出如何在Java中以良好的时间复杂度来完成这个任务了。

不，这不是一个简单的正则匹配( wrong)，，，但喜欢被证明)

我想要的是，

模式："1221“(意思是一个单词重复一次，第二个单词重复两次，最后一个单词和第一个单词相同)

有效输入："aabbbbbbaa“(aa发生在开头和结尾，而中间部分被bbb重复两次)

我尝试了下列方法，但不幸地失败了

• 我试着用模式循环输入。但是这并没有解决这个问题，虽然我可以用更多的循环来实现它，但是它以指数方式增加了时间复杂度。
• 尝试过递归，再一次没有用。

我还能尝试什么其他方法？

我认为动态规划可能是答案，但我无法确定终止条件。

任何帮助都将不胜感激。

Answer 1

您可以使用简单的正则表达式，例如：

^(.+)(.+)\2\1$

它做你想做的事：

​

​