public boolean wordPatternMatch(String pattern, String str) {
Map<Character, String> map = new HashMap<>();
Set<String> set = new HashSet<>();
return isMatched(pattern, 0, str, 0, set, map);
public boolean isMatched(String pattern, int patternIndex, String str, int strIndex, Set<String> set, Map<Character, String> map) {
if (patternIndex == pattern.length() && strIndex == str.length()) {
if (patternIndex == pattern.length() || strIndex == str.length()
|| str.length() - strIndex < pattern.length() - patternIndex) {
char c = pattern.charAt(patternIndex);
if (map.containsKey(c)) {
String matchedStr = map.get(c);
// 如果string剩余的部分并非以已匹配的string开头的话,则pattern不match
if (!str.startsWith(matchedStr, strIndex)) {
return isMatched(pattern, patternIndex + 1, str, strIndex + matchedStr.length(), set, map);
// 如果当前字符c目前没有匹配的string, 尝试match各种可能的string
for (int i = strIndex; i < str.length(); i++) {
String candidate = str.substring(strIndex, i + 1);
// 利用HashSet防止不同的字符对应一样的string
if (set.contains(candidate)) {
if (isMatched(pattern, patternIndex + 1, str, i + 1, set, map)) {