今天发现LintCode页面刷新不出来了，所以就转战LeetCode。还是像以前一样，做题顺序：难度从低到高，每天至少一题。
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.
Example 1:
Input: pattern ="abba", str ="dog cat cat dog"
Output: true
Example 2:
Input:pattern ="abba", str ="dog cat cat fish"
Output: false
Example 3:
Input: pattern ="aaaa", str ="dog cat cat dog"
Output: false
Example 4:
Input: pattern ="abba", str ="dog dog dog dog"
Output: false
Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.
解题：题目给定俩字符串，第一个字符串是由若干非空字符组成，第二个字符串由若干单词组成，用空白字符隔开。要求判断两组字符串格式是否相同。先贴一下自己写的代码吧，写的代码比较多，也没啥技术含量。最主要的思想是，遍历第一个字符串，比较各个位置上的字符是否相同，同时比较另一个字符串相同位置的单词是否相等，如果有不匹配的，返回false，遍历结束时，返回true。代码如下：
class Solution {
public boolean wordPattern(String pattern, String str) {
if(pattern == null && str == null)
return true;
String []temp = str.split(" ");
if(pattern.length() != temp.length)
return false;
if(pattern.length() ==1)
return true;
for(int i = 1; i < pattern.length(); i++){
for(int j = 0; j < i; j++){
if(pattern.charAt(i) == pattern.charAt(j)){
if(!equal(temp, i, j)){
return false;
}
}
if(pattern.charAt(i) != pattern.charAt(j)){
if(equal(temp, i, j)){
return false;
}
}
}
}
return true;
}
public boolean equal(String[]temp,int index1,int index2){
if(temp[index1].equals(temp[index2])){
return true;
}else{
return false;
}
}
}
}
在discussion上看到了更好的方法，用hash表来做的。hashmap中插入一组数据的方法是：public V put (K key, V value ) 如果插入一组数据时，已经有key存在，则返回 旧的value，并用新的value来覆盖旧的value。
那么用一个循环同时遍历两个String，如果相同位置有重复的，说明两个字符串匹配，反之，如果哪个位置上，一个字符串发现已经有这个key值了，另一个string却发现hashmap里并没有重复出现的key值，说明两个字符串的格式并不匹配。代码如下：
class Solution {
public boolean wordPattern(String pattern, String str) {
String[]words = str.split(" ");
if(pattern.length() != words.length)
return false;
Map map1=new HashMap();
Map map2=new HashMap();
for(int i = 0; i < pattern.length(); i++){
if((map1.put(pattern.charAt(i), i)) != map2.put(words[i], i))
return false;
}
return true;
}
}
由于此题把第二个字符串转化为了字符数组，那么遍历时及时字符和字符串内容相同，其类型也不相同，所以可以只用一个map。代码进一步化简为：
class 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;
}
}