291. Word Pattern II

JIAKAOBO

LeetCode

感谢赞助!

• ㊗️
• 大家
• offer
• 多多！

Problem

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.

Code

class Solution {
    public boolean wordPatternMatch(String pattern, String str) {
        HashMap<Character, String> map = new HashMap<>();
        HashSet<String> set = new HashSet<>();
        return isMatch(str, 0, pattern, 0, map, set);
    }

    private boolean isMatch(
        String str,
        int strIndex,
        String pattern,
        int patIndex,
        HashMap<Character, String> map,
        HashSet<String> set
    ){
        if(strIndex == str.length() && patIndex == pattern.length()){
            return true;
        }

        if(strIndex == str.length() || patIndex == pattern.length()){
            return false;
        }

        char c = pattern.charAt(patIndex);

        if(map.containsKey(c)){
            String s = map.get(c);
            if(!str.startsWith(s, strIndex)){
                return false;
            }

            return isMatch(str, strIndex + s.length(), pattern, patIndex + 1, map, set);
        }

        for(int i = strIndex; i < str.length(); i++){
            String temp = str.substring(strIndex, i + 1);
            if(set.contains(temp)){
                continue;
            }

            map.put(c, temp);
            set.add(temp);
            if(isMatch(str, i + 1, pattern, patIndex + 1, map, set)){
                return true;
            }

            map.remove(c);
            set.remove(temp);
        }

        return false;
    }
}