Problem statement

https://leetcode.com/problems/word-pattern-ii/

Solution

The idea is to use dfs with the following parameters

  1. id_p is index in pattern p
  2. id_s is index in string s
  3. d_ps is dictionary of connections in the direction p $\to$ s
  4. d_sp is dictionary of connections in the direction s $\to$ p

Next, we use idea of problem 0290 Word Pattern. We take one symbol from pattern and check different bijections.

  1. If this letter was not in d_ps, then we try to create new connections, take 1, 2, ... symbols from s. Make sure that string s[id_s:i+1] not in d_sp and then run dfs recursively: if at least for one option we have true, then return true.
  2. If this letter was already in d_ps, then check that we can continue string s and if we can, and anwer for subproblem is true, return true.
  3. If we never returned true, return false in the end.

Complexity

Time complexity can be estimated as $O(n \cdot C^{m-1}{n-1})$, space complexity is $O(m + n)$.

Code

class Solution:
    def wordPatternMatch(self, p, s):
        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, {}, {})