方法1:哈希表+双指针
时间复杂度:$O(n + m)$
空间复杂度:$O(n + m)$
解题思路
可参考更简单的205题。
Java 代码
class Solution {
public boolean wordPattern(String pattern, String s) {
Map<Character, String> ch2str = new HashMap<>();
Map<String, Character> str2ch = new HashMap<>();
//p遍历pattern。
//i和j遍历s,其中i为每个单词的起始位置,j为每个单词终止位置后的那个位置。
int i = 0, j = 0;
for (int p = 0; p < pattern.length(); p ++) {
char ch = pattern.charAt(p);
//注意i的边界条件。i可能提前走完
if (i >= s.length()) {
return false;
}
j = i;
while (j < s.length() && s.charAt(j) != ' ') {
j ++;
}
String tmp = s.substring(i, j);
if (ch2str.containsKey(ch) && !tmp.equals(ch2str.get(ch))) {
return false;
}
if (str2ch.containsKey(tmp) && str2ch.get(tmp) != ch) {
return false;
}
i = j + 1;
ch2str.put(ch, tmp);
str2ch.put(tmp, ch);
}
//排除掉p走完,i、j还没走完的特殊情况。
return j == s.length();
}
}