Problem statement

https://binarysearch.com/problems/Pattern-Matching/

Solution

Equal to Leetcode 0291. Word Pattern II.

Complexity

Time complexity can be estimated as O(n*C_{m-1}^{n-1}), space complexity is O(m + n)`.

Code

class Solution:
    def solve(self, s, p):
        m, n = len(p), len(s)
        
        def dfs(id_p, id_s, d_ps, d_sp):
            if id_s == n and id_p == m: return True
            if id_s == n or  id_p == m: return False

            new_letter = p[id_p]
            if new_letter not in d_ps:
                for i in range(id_s, n):
                    if s[id_s:i+1] not in d_sp:
                        d_ps[new_letter] = s[id_s:i+1]
                        d_sp[s[id_s:i+1]] = new_letter
                        if dfs(id_p + 1, i + 1, d_ps, d_sp): return True
                        d_ps.pop(new_letter)
                        d_sp.pop(s[id_s:i+1])
            else:
                corr = d_ps[new_letter]
                if s[id_s:].startswith(corr):
                    if dfs(id_p + 1, id_s + len(corr), d_ps, d_sp): return True
            
            return False
              
        return dfs(0, 0, {}, {})