Pattern matching : Matching a String with a pattern

Question

I was trying to match a pattern within a string. I am running out of ideas how to do this in Java with good time complexity.

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

What I am trying is,

Pattern : "1221" (Means 1 word repeat once, 2nd word repeat twice, last word is same as first word)

Valid Input: "aabbbbbbaa" (aa occurs at the beginning and at end, while middle portion is occupied by bbb repeating twice)

I tried the following approaches but failed miserably

• I tried to loop input with the pattern. But that did not solve the problem, although with more loops I can achieve it, but it increases the time complexity exponentially.
• Tried recursion and again no use.

What other approaches can I try?

I think Dynamic programming might be the answer, but I am not able to determine the terminating condition.

Any help would be appreciated.

Answer 1

You can use simple regex, e.g.:

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

It does exactly what u want: