290. Word Pattern

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:

1. pattern = "abba", str = "dog cat cat dog" should return true.
2. pattern = "abba", str = "dog cat cat fish" should return false.
3. pattern = "aaaa", str = "dog cat cat dog" should return false.
4. 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:

The idea is to create two HashMaps.

We first check the uniqueness between each character in the pattern to words in string using one HashMap.

Then we check the uniqueness between each words in the string to the character in the pattern using the second HashMap.

The reason to check twice is to handle such case:

"abcb" -> "dog cat dog cat"



Code:

public class Solution {
    public boolean wordPattern(String pattern, String str) {
        HashMap<Character, String> map1 = new HashMap<>();
        String[] strarr = str.split(" ");
        if (strarr.length != pattern.length()) {
            return false;
        }
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (!map1.containsKey(c)) {
                map1.put(c, strarr[i]);
            }
            else {
                if (!map1.get(c).equals(strarr[i])) {
                    return false;
                }
            }
        }
        HashMap<String, Character> map2 = new HashMap<>();
        for (int i = 0; i < pattern.length(); i++) {
            char c = pattern.charAt(i);
            if (!map2.containsKey(strarr[i])) {
                map2.put(strarr[i], c);
            }
            else {
                if (map2.get(strarr[i]) != c) {
                    return false;
                }
            }
        }
        return true;
    }
}