java - 模式匹配 : Matching a String with a pattern

Question

我试图匹配字符串中的模式。我想不出如何在 Java 中以良好的时间复杂度执行此操作。

No its not a simple regex matching (but loved to be proved wrong)

我正在尝试的是，

Pattern:“1221”(表示第一个单词重复一次，第二个单词重复两次，最后一个单词与第一个单词相同)

有效输入:“aabbbbbbaa”(aa出现在开头和结尾，而中间部分被bbb重复两次占据)

我尝试了以下方法但惨遭失败

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

我可以尝试哪些其他方法？

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

如有任何帮助，我们将不胜感激。

Answer 1

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

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

它完全符合你的要求: