LeetCode 291 - Word Pattern II

作者 QIFAN 日期 2017-02-14
LeetCode 291 - Word Pattern II

原题链接: 291. Word Pattern II


题干

给定一个字符串表示 pattern ,再给定一个字符串 str ,若 str 满足 pattern ,则返回 true 。

举例

  1. pattern = “abab”, str = “redblueredblue” should return true.
  2. pattern = “aaaa”, str = “asdasdasdasd” should return true.
  3. pattern = “aabb”, str = “xyzabcxzyabc” should return false.

思路

一些边界情况:

  • pattern 和 str 同时为空,返回 true
  • pattern 和 str 不同时为空,返回 false
  • pattern 长度大于 str ,返回 false

这些也就可以看成是递归时候的 base case 。储存一个 map 来保存每个 pattern 中的字母所代表的字符串,如果存在,则看后续与存着的值是否一致,不一致返回 false ,如果一致,则 pattern 往后一步,str 往后相应长度,进行下一轮递归。这样子把边界情况修改如下:

int pIndex; // pattern index
int sIndex; // str index
int patternL; // pattern length
int strL; // str length
if (pIndex == patternL && sIndex == strL) return true
if (pIndex == pattern || sIndex == strL) return false
if (patternL - 1 - pIndex > strL - 1 - sIndex) return false

写代码的途中也进行了一些 test ,但是最后还是有两个关键 case 没有想到导致 bug 和两次失败提交:

  • “” “” true
  • “ab” “” false // 一个字母不能代表空字符串
  • “ab” “aa” false // 不同字母不能代表同一串字符
  • (遗漏)”a” “b” true // substring 初始位置是当前的后一位。
  • (遗漏)”aa” “xyz” false // arrayoutoflength 错误

代码:

public boolean wordPatternMatch(String pattern, String str) {
if (pattern == null || str == null) {
return false;
}
if (pattern.length() == 0 && str.length() == 0) {
return true;
}
if (pattern.length() == 0 || str.length() == 0 || pattern.length() > str.length()) {
return false;
}
HashMap<Character, String> patternMap = new HashMap<>();
return matchPattern(pattern, 0, str, 0, patternMap);
}
private boolean matchPattern(String pattern, int pIndex, String str, int sIndex, HashMap<Character, String> patternMap) {
int pLeft = pattern.length() - pIndex; // pattern 剩余
int sLeft = str.length() - sIndex; // str 剩余
// base case 1 全部用完
if (pLeft == 0 && sLeft == 0) {
return true;
}
// base case 2 其中一个用完或者 pattern 剩的比 str 多
if (pLeft == 0 || sLeft <= 0 || pLeft > sLeft) {
return false;
}
int sLength = str.length();
char key = pattern.charAt(pIndex);
// 如果存在 key
if (patternMap.containsKey(key)) {
String s = patternMap.get(key);
// 如果超过了边界,返回 false
if (sIndex + s.length() > sLength) {
return false;
}
// 如果相等,进行后面的匹配
if (s.equals(str.substring(sIndex, sIndex + s.length()))) {
if (matchPattern(pattern, pIndex + 1, str, sIndex + s.length(), patternMap)) {
return true;
}
}
// 不存在 key
} else {
// 尝试当前 key 匹配所有的substring,match 的直接返回 true
for (int i = sIndex + 1; i <= sLength; i++) {
String substring = str.substring(sIndex, i);
if (existInMap(substring, patternMap)) {
continue;
}
patternMap.put(key, substring);
if (matchPattern(pattern, pIndex + 1, str, i, patternMap)) {
return true;
}
patternMap.remove(key); // 记得移除出 map
}
}
return false;
}
// 检查该 string 是否已经由另一个 key 表示
private boolean existInMap(String s, HashMap<Character, String> patternMap) {
for (Map.Entry<Character, String> pair: patternMap.entrySet()) {
if (s.equals(pair.getValue())) {
return true;
}
}
return false;
}

提升空间:

  • 可以再用一个 Set 来存已经有的 pattern ,不用每次都遍历。
  • 不用 index 作为参数直接传 substring 应该更快一些,毕竟直接从程序栈里读取而不是 memory