Word Pattern

Problem

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:
pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.

Notes: You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Solution

Hash Table Solution: O(n ^ 2) time (because of containsValue() method), O(n) space containsKey() is O(1) time

public class Solution {
    public boolean wordPattern(String pattern, String str) {
        String[] words = str.split(" ");
        if (words.length != pattern.length()) return false;
        Map<Character, String> map = new HashMap<>();
        for (int i = 0; i < words.length; i++) {
            char key = pattern.charAt(i);
            String value = words[i];
            if (map.containsKey(key) && !map.get(key).equals(value)) return false;
            if (!map.containsKey(key) && map.containsValue(value)) return false;
            map.put(key, value);
        }
        return true;
    }
}

Analysis

We use a HashMap in this solution to store the corresponding pattern with its value
We first use split() to get each word in given str
Then we loop through the pattern and get key pattern and value word
If it contains key, but value does not equal, we return false
Or if it does not contain key, but contains value, we return false as well At the end, we return true