There's an interesting question I came across online, which basically asks the following:
Given a pattern and a string input, find if the string follows the same pattern and return 'True' or 'False'. Examples:
- Pattern: "abba", input: "redblueredblue" should return 'True'
- Pattern: "aaaa", input: "asdasdasdasd" should return 'True'
- Pattern: "aabb", input: "xyzabcxzyabc" should return 'False'
Turns out that the solution to this question is an algorithm that takes time that's exponential in the size of the input 'text' in the worst case. This is because we need to test every possible substring to check if it could be a substitution for a pattern letter.
Here is some Python code that solves it using Python regexes (these are more powerful compared to Posix Regular Expressions, since they allow you to use backreferences). The solution relies heavily on the backtracking capabilities of the python regex execution engine (PCRE).