Problem

Given a pattern and a string str, find if str 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 str.

Example 1:

Input: pattern = "abab", str = "redblueredblue"

Input: pattern = pattern = "aaaa", str = "asdasdasdasd"

Input: pattern = "aabb", str = "xyzabcxzyabc"

Solution

class Solution {    public boolean wordPatternMatch(String pattern, String str) {        if (pattern == null || str == null || str.length() < pattern.length()) return false;        Map
    
      map = new HashMap<>();        return helper(pattern, 0, str, 0, map);    }    private boolean helper(String pattern, int i, String str, int j, Map
     
       map) {        if (i == pattern.length() && j == str.length()) return true;        if (i == pattern.length() || j == str.length()) return false;                char ch = pattern.charAt(i);                if (map.containsKey(ch)) {            String s = map.get(ch);            if (!str.substring(j).startsWith(s)) return false;            else return helper(pattern, i+1, str, j+s.length(), map);        } else {            //try put some str substrings into the map            for (int k = j; k < str.length(); k++) {                String part = str.substring(j, k+1);                if (map.containsValue(part)) continue; //already used by a different key                                //add the new pair, dfs, remove the new pair (backtracking)                map.put(ch, part);                if (helper(pattern, i+1, str, k+1, map)) return true;                map.remove(ch);            }        }                return false;    }}