291. Word Pattern II

Description

Given a pattern and a string s, return true if s matches the pattern.

A string s matches a pattern if there is some bijective mapping of single characters to non-empty strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

Example 1:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

Example 2:

Input: pattern = "aaaa", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "asd"

Example 3:

Input: pattern = "aabb", s = "xyzabcxzyabc"
Output: false

Constraints:

1 <= pattern.length, s.length <= 20
pattern and s consist of only lowercase English letters.

Solutions

This solution code defines a solution to a pattern matching problem, where the goal is to determine if a given string s can be segmented in a way that matches a given pattern pattern. Each character in pattern represents a distinct part of s, and the same character in pattern should map to the same segment in s.

The solution employs Depth-First Search (DFS) to explore all possible ways of segmenting s to match the pattern. Here’s a detailed breakdown of how the code works:

Function: `wordPatternMatch`

Parameters: It takes a pattern (a string where each character represents a pattern to match) and s (the string to be matched against the pattern).

Helper Function: `dfs`

Purpose: The dfs function is a recursive helper function that attempts to match the pattern with segments of s. It uses two additional lists, pathp and paths, to keep track of the current segment mappings from pattern to s.
Base Case: The recursion ends successfully (return True) if both p (remaining pattern) and s (remaining string) are empty, meaning a complete match has been found. It returns False if p is empty but s is not, or if the remaining pattern length is greater than the remaining string length, indicating a mismatch.
Recursion and Backtracking:
- The function iterates through s, trying to match the current character in pattern (p[0]) with every possible leading segment of s.
- At each iteration, it adds the current pattern character to pathp and the current segment being considered (s[:i + 1]) to paths.
- It checks for a valid mapping: if the lengths of pathp and paths are equal, and the number of unique elements in paths, pathp, and their zipped combination (pairs of pattern and corresponding segment) are the same. This condition ensures that each character in the pattern maps to a unique and consistent segment in s.
  - If the condition is met, it recursively calls dfs with the next character in the pattern and the remaining string, excluding the current segment.
  - If the recursive call returns True, indicating a successful match for the remaining pattern and string, the current call also returns True.
- Implements backtracking by removing the last added elements from pathp and paths before moving to the next iteration.
- Returns False if no valid mapping is found for any segment of s against the current character in pattern.

Return Value

The initial call to dfs starts with the full pattern and s, along with empty lists for pathp and paths. The return value of this call determines whether a valid pattern match exists for the entire string s.

class Solution {
    private Set<String> vis;
    private Map<Character, String> d;
    private String p;
    private String s;
    private int m;
    private int n;

    public boolean wordPatternMatch(String pattern, String s) {
        vis = new HashSet<>();
        d = new HashMap<>();
        this.p = pattern;
        this.s = s;
        m = p.length();
        n = s.length();
        return dfs(0, 0);
    }

    private boolean dfs(int i, int j) {
        if (i == m && j == n) {
            return true;
        }
        if (i == m || j == n || m - i > n - j) {
            return false;
        }
        char c = p.charAt(i);
        for (int k = j + 1; k <= n; ++k) {
            String t = s.substring(j, k);
            if (d.getOrDefault(c, "").equals(t)) {
                if (dfs(i + 1, k)) {
                    return true;
                }
            }
            if (!d.containsKey(c) && !vis.contains(t)) {
                d.put(c, t);
                vis.add(t);
                if (dfs(i + 1, k)) {
                    return true;
                }
                vis.remove(t);
                d.remove(c);
            }
        }
        return false;
    }
}

class Solution {
public:
    bool wordPatternMatch(string pattern, string s) {
        unordered_set<string> vis;
        unordered_map<char, string> d;
        return dfs(0, 0, pattern, s, vis, d);
    }

    bool dfs(int i, int j, string& p, string& s, unordered_set<string>& vis, unordered_map<char, string>& d) {
        int m = p.size(), n = s.size();
        if (i == m && j == n) return true;
        if (i == m || j == n || m - i > n - j) return false;
        char c = p[i];
        for (int k = j + 1; k <= n; ++k) {
            string t = s.substr(j, k - j);
            if (d.count(c) && d[c] == t) {
                if (dfs(i + 1, k, p, s, vis, d)) return true;
            }
            if (!d.count(c) && !vis.count(t)) {
                d[c] = t;
                vis.insert(t);
                if (dfs(i + 1, k, p, s, vis, d)) return true;
                vis.erase(t);
                d.erase(c);
            }
        }
        return false;
    }
};

class Solution(object):
  def wordPatternMatch(self, pattern, s):
    """
    :type pattern: str
    :type s: str
    :rtype: bool
    """

    # pathp: path for pattern
    # paths: path for matched strings
    def dfs(p, s, pathp, paths):
      if len(p) == len(s) == 0:
        return True
      if len(p) == 0 or len(p) > len(s):
        return False
      for i in range(0, len(s)):
        pathp.append(p[0])
        paths.append(s[:i + 1])
        # same as in Word-Pattern-I, for checking if valid
        if len(pathp) == len(paths) and len(set(paths)) == len(set(pathp)) == len(set(zip(paths, pathp))):
          if dfs(p[1:], s[i + 1:], pathp, paths):
            return True
        pathp.pop()
        paths.pop()
      return False

    return dfs(pattern, s, [], [])

############

'''
>>> d = {}
>>> d.get('a')
>>>
>>> r = d.get('a')
>>> r
>>>
>>> if not r:
...     print('aa')
aa
'''
class Solution:
    def wordPatternMatch(self, pattern: str, s: str) -> bool:
        def dfs(i, j):
            if i == m and j == n:
                return True
            if i == m or j == n or n - j < m - i:
                return False
            for k in range(j, n):
                t = s[j: k + 1]
                if pattern[i] in d and d[pattern[i]] == t:
                    if dfs(i + 1, k + 1):
                        return True
                elif pattern[i] not in d and t not in vis:
                    d[pattern[i]] = t
                    vis.add(t)
                    if dfs(i + 1, k + 1):
                        return True
                    d.pop(pattern[i])
                    vis.remove(t)
            return False

        m, n = len(pattern), len(s)
        d = {}
        vis = set()
        return dfs(0, 0)

func wordPatternMatch(pattern string, s string) bool {
	m, n := len(pattern), len(s)
	vis := map[string]bool{}
	d := map[byte]string{}
	var dfs func(i, j int) bool
	dfs = func(i, j int) bool {
		if i == m && j == n {
			return true
		}
		if i == m || j == n || m-i > n-j {
			return false
		}
		c := pattern[i]
		for k := j + 1; k <= n; k++ {
			t := s[j:k]
			if v, ok := d[c]; ok && v == t {
				if dfs(i+1, k) {
					return true
				}
			}
			if _, ok := d[c]; !ok && !vis[t] {
				d[c] = t
				vis[t] = true
				if dfs(i+1, k) {
					return true
				}
				delete(d, c)
				vis[t] = false
			}
		}
		return false
	}
	return dfs(0, 0)
}

291 - Word Pattern II

291. Word Pattern II

Description

Solutions

Function: `wordPatternMatch`

Helper Function: `dfs`

Return Value

All Problems

All Solutions

Welcome to Subscribe On Youtube

291. Word Pattern II

Description

Solutions

Function: wordPatternMatch

Helper Function: dfs

Return Value

All Problems

All Solutions

Function: `wordPatternMatch`

Helper Function: `dfs`