Word Pattern Ii - Leetcode Solution

Problem Description:

Given a pattern and a string s, find if s follows the same pattern.

Here, "follow" means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in s.

Example 1: Input: pattern = "abab", s = "redblueredblue" Output: true Explanation: One possible mapping from 'abab' to 'redblueredblue' is: 'a' -> "red" 'b' -> "blue" Note that 'a' and 'b' cannot map to the same string since they are different.

Example 2: Input: pattern = "aaaa", s = "asdasdasdasd" Output: true Explanation: One possible mapping from 'aaaa' to 'asdasdasdasd' is: 'a' -> "asd" Note that 'a' must map to a substring with length 1.

Example 3: Input: pattern = "abab", s = "redredredred" Output: false Explanation: Cannot find any possible mapping from 'abab' to 'redredredred'.

Solution:

This problem is similar to the word pattern problem, except that instead of a character mapping to a single word, a character can map to multiple substrings in the string. We can solve this problem by using recursion.

We can start by selecting the first character of the pattern and looping through all possible substrings of the input string that start with this character. For each substring, we can check if it has been used before or not (since each character in the pattern can only map to a non-empty substring once).

If the current character has not been used before, we can add it to our mapping list and recursively call the function with the remaining pattern and string.

If the current character has been used before, we can check if the substring matches the mapped value. If it does, we can recursively call the function with the remaining pattern and string. If it does not, we return false.

If we have mapped all characters successfully, we check if there are any characters in the remaining pattern or string. If the pattern is empty and the string is also empty, we return true. Otherwise, we return false.

Here's the Python code for the solution:

def wordPatternMatch(pattern, s): def dfs(p, s, mapping): if not p and not s: return True if not p or not s: return False char = p[0] if char in mapping: if s.startswith(mapping[char]): return dfs(p[1:], s[len(mapping[char]):], mapping) else: return False for i in range(1, len(s)-len(p)+2): if s[:i] in mapping.values(): continue mapping[char] = s[:i] if dfs(p[1:], s[i:], mapping): return True del mapping[char] return False return dfs(pattern, s, {})

1