Blog Details

Word Pattern

1. Description

Give a pattern and a string, and check if the string follows the pattern.

2. Example

pattern: "aabb"
str: "hello hello world world" 
Output: true

pattern: "abbc"
str: "dog cat cat fish"
Output: true

pattern: "bbb"
str: "cat dog cat"
output: false

3. Solution

3.1 Wrong solution

First, I was thinking, if I can use the AscII code to represent the pattern. For example: hello -> ‘a’, and hello -> ‘a’, world -> ‘b’, world->’b’.

Use the data structure ArrayList to store each string, if it exist in the list, use list quickly get the pattern.

But this solution only applies the pattern starting from ‘a’. However, the pattern can be in any letter. For example, the first example still follows the pattern “syys”.

3.2 Correct solution

Use two HashMap.

Let’s use the example: pattern: “aabb”, and str: “hello hello world world”.

HashMap #1: (‘a’, “hello”), (“a”, “hello”), (“b”, “world”), (“b”, “world”).

HashMap #2: (“hello”, ‘a), (“hello”, ‘a’)…. // a reverse HashMap.

The reason doing this is there isn’t an API to get the key according to the object value.

Time Complexity: O(n) linear complexity.

class Solution {
    public boolean wordPattern(String pattern, String str) {
        // map 1
        HashMap<Character, String> map = new HashMap<Character, String>();
        // reverse map
        HashMap<String, Character> reverseMap = new HashMap<String, Character>(); 
        String[] strs = str.split(" ");
        
        for(int i = 0; i < strs.length; i ++) {
            if(pattern.length() <= i || pattern.length() > strs.length) {
                return false;
            }
            if(!map.containsValue(strs[i]) && !reverseMap.containsValue(pattern.charAt(i))) {
                map.put(pattern.charAt(i), strs[i]);
                reverseMap.put(strs[i], pattern.charAt(i));
            }  else {
                if(!reverseMap.containsKey(strs[i])) {return false;}
                char ch = reverseMap.get(strs[i]);
                if(ch != pattern.charAt(i)) {
                    return false;
                }
                map.put(ch, strs[i]);
                reverseMap.put(strs[i], ch);
            }
        }
        return true;
    }
}