leetcode面试准备: Word Pattern
1 题目
Given a pattern and a string str, find if str follows the same pattern.
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:
patterncontains only lowercase alphabetical letters, and str contains words separated by a single space. Each word in str contains only lowercase alphabetical letters.
Both pattern and str do not have leading or trailing spaces.
Each letter in pattern must map to a word with length that is at least 1.
接口: public boolean wordPattern(String pattern, String str)
2 思路
题意
通过pattern来匹配单词，很容易想到HashMap思想。
注意
-
pattern的长度，不对应str拆分单词后的长度。 - 一个
pattern字母和唯一一个字符串相互对应。
复杂度: Time:O(n) Space: O(n)
3 代码
public boolean wordPattern(String pattern, String str) {
String[] words = str.split("\\s", -1);
int len = words.length;
if (pattern.length() != len) { // 长度不等直接false，防止后面数组越界
return false;
}
Map<Character, String> map = new HashMap<>(26);
for (int i = 0; i < len; i++) {
Character c = pattern.charAt(i);
if (map.containsKey(c)) {
if (!map.get(c).equals(words[i]))
return false;
} else {
if (map.containsValue(words[i])) { // 字母和字符串一一对应。
return false;
}
map.put(c, words[i]);
}
}
return true;
}
4 总结
简单题，注意细节。一次AC。