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.

My solution:

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

Other's solution:

public boolean wordPattern(String pattern, String str) {
    String[] words = str.split(" ");
    if (words.length != pattern.length())
        return false;
    Map index = new HashMap();
    for (Integer i=0; i<words.length; ++i)
        if (index.put(pattern.charAt(i), i) != index.put(words[i], i))
            return false;
    return true;
}

I go through the pattern letters and words in parallel and compare the indexes where they last appeared.

The return value of put method is the Value associates with the specified key in the map.

Paste_Image.png