Word Pattern

Easy15–20 min

Topics

HashMapString

Companies

GoogleDropboxUber

Given a pattern of characters and a space-separated string s, determine whether s follows the same pattern — where each character in pattern maps to exactly one word in s, and each word maps back to exactly one character (a full one-to-one, bijective mapping).

Test Case 1:

Input:pattern = "xyxz", s = "cat dog cat bird"

Output:true

Explanation:x always maps to cat, and every other position is consistent — a valid bijection.

Test Case 2:

Input:pattern = "xyx", s = "sun moon moon"

Output:false

Explanation:x maps to sun at position 0, but position 2 pairs x with moon instead.

Test Case 3:

Input:pattern = "xy", s = "sun sun"

Output:false

Explanation:Both x and y would need to map to sun — not a one-to-one mapping.

Constraints

◆1 ≤ pattern.length ≤ 10
◆pattern consists of lowercase English letters
◆s consists of lowercase English letters and single spaces, with no leading or trailing spaces
◆1 ≤ number of words in s ≤ 10

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Parallel Arrays, Linear Lookup

Good

Split s into words. Instead of a hash map, keep two plain lists — one of characters seen so far, one of the words they were paired with — in the same order. For each pattern character and word, scan the lists to see if either has already been paired with something else, and reject if so; otherwise, if neither has been seen, append the new pair. It's a direct simulation of "have I paired this before?", but every check re-scans the lists from the start, so the work grows with the square of the pattern length.

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public boolean wordPattern(String pattern, String s) {
        String[] words = s.split(" ");
        if (pattern.length() != words.length) return false;
        List<Character> mappedChars = new ArrayList<>();
        List<String> mappedWords = new ArrayList<>();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            String w = words[i];
            int charSeenAt = mappedChars.indexOf(c);
            int wordSeenAt = mappedWords.indexOf(w);
            if (charSeenAt != -1 && !mappedWords.get(charSeenAt).equals(w)) return false;
            if (wordSeenAt != -1 && mappedChars.get(wordSeenAt) != c) return false;
            if (charSeenAt == -1 && wordSeenAt == -1) {
                mappedChars.add(c);
                mappedWords.add(w);
            }
        }
        return true;
    }
}

Optimal — Two HashMaps, Single Pass

Optimal

A valid pattern needs a two-way (bijective) mapping, so track both directions at once with two hash maps: charToWord and wordToChar. Walk the pattern and words together; if the current character is already mapped to a different word, or the current word is already mapped to a different character, the pattern breaks — reject immediately. Otherwise record both mappings and continue. Every check is an O(1) hash map lookup, so the whole pass is linear.

TimeO(n)