# Share my Java solution, Use dfs to solve an equation of token length and then match

• My idea is to analyze the pattern first. I used an array of length 26 to store the appearance times of a particular character. For the pattern "abab", the array called times would be like

[2, 2, 0, 0, 0, 0, ..... Many zeros]

Then I tried to solve an equation on the str length.

2 * x + 2 * y = 14;

I used dfs to solve this problem. After I have all the permutations, for example in case "abab", "redblueredblue" permute array would be [2, 12, 0, 0, 0, 0, .... Many zeros]. So I know that for char a, the length is 2 / 2 = 1. The length for b is 12 / 2 = 6. Then I match these two string using a similar approach in Word Pattern 1.

A better way could do so is to whenever a result permutation comes out, check 2 strings at once. Thus avoid lots of dfs calls.

For the time complexity, I am not quite sure, if you know, please analyze for me. I guess it is O(n^2) as the pattern length need to gradually grow to the string length.

``````public boolean wordPatternMatch(String pattern, String str) {
int pLen = pattern.length();
int sLen = str.length();

if (pLen == 0 && sLen == 0) {
return true;
}

if (pLen <= 0) {
return false;
}

if (sLen <= 0) {
return false;
}

List<int[]> results = new ArrayList<>(256);
int[] permute = new int[26];
Arrays.fill(permute, 0);
for (int i = 0; i < pLen; i++) {
int index = pattern.charAt(i) - 'a';
permute[index]++;
}
int[] times = new int[26];
System.arraycopy(permute, 0, times, 0, 26);
dfs(results, permute, sLen - pLen, 0, times);

int size = results.size();
HashMap<Character, String> pToS = new HashMap<>(pLen * 2);
HashMap<String, Character> sToP = new HashMap<>(pLen * 2);
for (int j = 0; j < size; j++) {
int[] pmt = results.get(j);

pToS.clear();
sToP.clear();
boolean success = true;
int start = 0;
int end = 0;
for (int i = 0; i < pLen; i++) {
char p = pattern.charAt(i);
int index = p - 'a';
end = start + pmt[index] / times[index];
String s = str.substring(start, end).intern();
start = end;
boolean ps = pToS.containsKey(p);
boolean sp = sToP.containsKey(s);

if (ps && sp) {
if (p == sToP.get(s) && s == pToS.get(p)) {
continue;
} else {
success = false;
break;
}
} else if (ps) {
success = false;
break;
} else if (sp) {
success = false;
break;
} else {
pToS.put(p, s);
sToP.put(s, p);
}
}

if (success) {
return true;
}
}

return false;
}

public void dfs(List<int[]> results, int[] permute, int lenLeft, int pos, int[] times) {
if (pos >= 26) {
if (lenLeft == 0) {
}
return;
}

if (lenLeft == 0) {
return;
}

if (permute[pos] <= 0) {
dfs(results, permute, lenLeft, pos + 1, times);
return;
}

int loopTimes = lenLeft / times[pos] + 1;
for (int i = 0; i < loopTimes; i++) {
int[] newPermute = new int[26];
System.arraycopy(permute, 0, newPermute, 0, 26);
newPermute[pos] = newPermute[pos] + times[pos] * i;
dfs(results, newPermute, lenLeft - times[pos] * i, pos + 1, times);
}
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.