Problem statement
Decide whether replacing each pattern character with a nonempty substring can form the entire input string. The mapping is bijective: one symbol always means the same word, and two different symbols cannot mean the same word.
For abab and redblueredblue, a→red and b→blue is one witness. This is not the simpler space-separated Word Pattern question: words here have no separators and can have different lengths.
The supplied task limits both strings to 1–20 lowercase letters. LeetCode Word Pattern II may require Premium; the algorithm below is complete without an account.
Constraints & requirements
- CONTRACT
- Original task: both strings have length 1–20 and lowercase letters. Mappings are bijective, substrings may have different lengths, and both inputs must be fully consumed. LeetCode may require Premium.
Examples 3 test cases
Example 1 Case 1
- Input
pattern="abab"; s="redblueredblue"- Output
true
One valid mapping is a→red and b→blue.
Example 2 Case 2
- Input
pattern="ab"; s="aa"- Output
false
Both nonempty parts would be a, violating the two-way mapping.
Example 3 Case 3
- Input
pattern="aaaa"; s="asdasdasdasd"- Output
true
Every a uses the same substring asd.
Hints Optional
01Hint 1
A known symbol must reuse its assigned word.
02Hint 2
For a new symbol, try every nonempty substring starting here.
03Hint 3
Use a map plus a used-word set; undo both when a choice fails.
How to think before coding
Track both pattern position and string position. A known symbol must reuse its exact word here; a new symbol tries nonempty prefixes of the remaining text. A map enforces same-symbol consistency and a used-word set enforces different-symbol uniqueness. Add BOTH reservations before descending and undo both after failure. Success requires consuming both inputs, not just one.
Brute force and the improvement
Cut the input string into as many nonempty pieces as there are pattern positions. For every complete cut placement, check whether equal symbols have equal pieces and different symbols have different pieces. With input length N and M pattern positions, there are C(N−1,M−1) placements when N≥M; a conservative O(N²) bijection check per placement gives O(N²·C(N−1,M−1)) time and O(N+M) working storage, excluding copied candidates. Reject inconsistent symbol assignments incrementally instead of waiting for every cut. The improved search remains exponential in the general case.
Intuition: try where the next word ends
When a symbol is already mapped, there is no decision to make. The remaining input must begin with its assigned word. If it does not, this branch fails.
For a new symbol, the word’s endpoint is unknown. Try each nonempty prefix of the remaining input: r, re, red, and so on. Remember the assignment, explore the rest, then undo it if it fails.
The map enforces “same symbol, same word.” A separate used-word set enforces the opposite direction, “different symbols, different words.” With only the map, pattern ab could incorrectly match aa by assigning both symbols to a.
Algorithm
- Track pi, the next pattern position, and si, the next input position.
- Accept only if both inputs finish together; reject if only one finishes.
- Reuse an existing symbol’s assigned word and advance by its length.
- Otherwise try every nonempty substring starting at si.
- Reject already-used words, temporarily assign a fresh one, and recurse.
- Return immediately on success; after failure remove both map and set entries.
Java solution
The map enforces a symbol’s assigned word and the set enforces word uniqueness across symbols. Candidate words need not have equal lengths.
import java.util.*;
class Solution {
public static boolean wordPatternMatch(String pattern, String s) {
return matchWords(pattern, s, 0, 0, new HashMap<>(), new HashSet<>());
}
private static boolean matchWords(String pattern, String s, int pi, int si,
Map<Character, String> map, Set<String> used) {
if (pi == pattern.length() || si == s.length()) { // A match must consume BOTH inputs.
return pi == pattern.length() && si == s.length();
}
char symbol = pattern.charAt(pi);
String assigned = map.get(symbol);
if (assigned != null) { // An existing symbol cannot change its meaning.
return s.startsWith(assigned, si)
&& matchWords(pattern, s, pi + 1, si + assigned.length(), map, used);
}
for (int end = si + 1; end <= s.length(); end++) { // Nonempty substrings, end exclusive.
String candidate = s.substring(si, end);
if (used.contains(candidate)) continue; // Different symbols cannot share a word.
map.put(symbol, candidate); used.add(candidate); // Choose a temporary bijection entry.
if (matchWords(pattern, s, pi + 1, end, map, used)) return true; // One witness suffices.
map.remove(symbol); used.remove(candidate); // Undo BOTH directions after failure.
}
return false; // Every assignment at this state failed.
}
public static void main(String[] args) {
System.out.println(wordPatternMatch("abab", "redblueredblue")); // true
}
}The invocation returns true. On successful short-circuiting, cleanup is unnecessary because the whole method exits and its private map/set are discarded. Failed paths must still clean up before trying siblings.
Search branches and dry run

Read the text transcript
Follow the Java, step by step
Example: pattern = "aba", s = "redbluered"
What to track: pi and si are consumed-prefix lengths. map assigns symbols to nonempty strings; used prevents two symbols sharing a string. Shorter assignments are tried before the successful one.
-
Try a short temporary assignment
Java operationmap.put(symbol, candidate); used.add(candidate);Statepi = 0; si = 0; candidate = "r"; map = {a:"r"}; used = {"r"}This is a guess, not a permanent mapping. The child tries every legal b substring.
-
Undo an exhausted guess
Java operationmap.remove(symbol); used.remove(candidate);Stateafter the a→"r" subtree fails: root map = {}; used = {}No b choice can consume the whole string and leave a final "r" match. The root must remove both reservations. The a→"re" subtree also fails.
-
Try the successful a prefix
Java operationmatchWords(pattern, s, pi + 1, end, map, used)Statea→"red"; child pi = 1, si = 3; map = {a:"red"}The root now chooses end = 3. Its child must assign b from the remaining "bluered".
-
Find b after shorter b guesses fail
Java operationString candidate = s.substring(si, end);Stateat pi = 1, si = 3: candidate = "blue" when end = 7The shorter b candidates leave the next characters unable to match the existing a assignment. Each failed guess is removed before this one is tried.
-
Reuse, rather than reassign, a
Java operations.startsWith(assigned, si)Statepi = 2; si = 7; assigned = "red"; suffix at 7 is "red"The existing mapping matches, so the child advances by exactly assigned.length(). It does not invent a different meaning for a.
-
Require both inputs to be exhausted
Java operationreturn pi == pattern.length() && si == s.length();Statepi = 3; si = 10; both equal their lengths; return trueSuccess short-circuits the waiting calls. Unlike enumeration, there is no need to explore or undo a successful private search map.
Final result: true, witnessed by a→"red" and b→"blue".
The implementation tries shorter substrings first. This table follows one successful branch after earlier failed assignments have been undone; it is not the complete traversal log.
| pi / si | Symbol | Action | Next indices |
|---|---|---|---|
| 0 / 0 | a, new | Assign red | 1 / 3 |
| 1 / 3 | b, new | Assign blue | 2 / 7 |
| 2 / 7 | a, known | Input begins with red; reuse it | 3 / 10 |
| 3 / 10 | b, known | Input begins with blue; reuse it | 4 / 14 |
| 4 / 14 | Both finished | Return true | Done |
For ab and aa, choosing a→a leaves one a for b. That word is already used, so the branch fails. Choosing a→aa consumes the string before the pattern finishes and also fails.
Why it works
The map and used set remain mutually consistent on every active branch. Known symbols cannot change meaning; new symbols cannot steal a used word. Every possible nonempty endpoint is tried, so no valid assignment is missed. Finishing both inputs proves the substitutions reconstruct exactly the whole string, not merely its prefix.
Complexity and alternative approaches
This search is exponential in general. Let M be pattern length, N input length and A the number of candidate/mapped-word checks actually visited. A check may copy, hash or compare O(N) characters, giving a useful bound O(N·A).
A loose worst-case bound is O(M·N^(M+1)): there are at most N choices per newly mapped symbol and at most M levels. It is intentionally loose; remaining-length constraints and repeated symbols cut many branches. Do not present O(M+N) or memoize only (pi,si): the current assignments also affect future validity.
Live assigned strings total O(N) characters along a path, plus O(M) frames and map/set entries. Candidate strings add O(N) transient storage. A length-feasibility prune can require enough remaining characters for every unmatched pattern occurrence, but should account for already-known word lengths.
Common mistakes
- Using only a map and forgetting injectivity.
- Allowing empty substrings, which changes the task and its termination reasoning.
- Accepting when just the pattern finishes.
- Not undoing used after undoing map.
- Assuming all pattern characters map to equally sized words.