题目：
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:
"abba", str = "dog cat cat dog" should return true."abba", str = "dog cat cat fish" should return false."aaaa", str = "dog cat cat dog" should return false."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.
链接： http://leetcode.com/problems/word-pattern/
题解：
跟Isomophic Strings基本一样，使用两个hashmap保持pattern char和string的的一对一关系。 看到Discuss里也有使用一个HashMap的，非常巧妙，对put研究得很深。二刷要使用更好的方法。
Time Complexity- O(n)， Space Complexity - O(n)。
public class Solution { private Map<Character, String> patternToStr; private Map<String, Character> strToPattern; public boolean wordPattern(String pattern, String str) { int len = pattern.length(); String[] arrOfStr = str.split(" "); if(len != arrOfStr.length) { return false; } patternToStr = new HashMap<>(); strToPattern = new HashMap<>(); for(int i = 0; i < len; i++) { char c = pattern.charAt(i); if(!patternToStr.containsKey(c) && !strToPattern.containsKey(arrOfStr[i])) { patternToStr.put(c, arrOfStr[i]); strToPattern.put(arrOfStr[i], c); } else if(patternToStr.containsKey(c) && !arrOfStr[i].equals(patternToStr.get(c))) { return false; } else if(strToPattern.containsKey(arrOfStr[i]) && c != strToPattern.get(arrOfStr[i])) { return false; } } return true; } }
Reference:
https://leetcode.com/discuss/62374/8-lines-simple-java
https://leetcode.com/discuss/62876/very-fast-3ms-java-solution-using-hashmap
原文：http://www.cnblogs.com/yrbbest/p/5042115.html