• ㊗️
• 大家
• 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);