LC: Word Pattern II - spiralgo/algorithms GitHub Wiki

Word Pattern II

The Essence:

When the prefix of the given string is to matched with the first character of the pattern, then the remaining part of the total matching is equivalent to matching the suffix of the strings with the remaining part of the pattern.

In the simplest terms: can_match(str, pattern) = for some prefix, can_match(suffix, pattern[1:])

Of course, the matching is bijective. When a prefix is matched to character, no other next prefix can be matched to it.

Details:

Since many prefixes of the current string will be tested, and a base case for the recursive testing is present, what naturally should come to mind is backtracking strategy.

Further detailed explanation and the code can be found here: https://github.com/spiralgo/algorithms/pull/328