[leetcode] Regular Expression Matching | 看string a是否match regex b

Posted by: lexigrey on: August 25, 2013

• In: leetcode
• 1 Comment

example: aabc matches c*a*b.

思路：

1. 两个指针i, j，i指regular expression，j指真的string。
2. 观察p[i+1]，
   • 如果它不是*，说明没法skip p[i]，则p[i]和s[j]必须match（相等或者p[i]是’.’ which matches everything）。如果不满足，直接返回false，没法matche了。
   • 如果它是*，说明当前位置可以是0个p[i], 1个p[i], 2个p[i]..
     1. 先试试“用0个p[i]“，即把p[i]和他后面的* skip掉。若recurse (i + 2, j)成功了，直接返回true，不成功，接着做第二步。
     2. 从“用1个p[i]“开始while循环，若p[i]和s[j] match, recurse on (i + 2, j + 1)（把*用掉了所以i+2），如果返回true就直接成了，否则就while继续循环“用2个p[i]“，即recurse on (i + 2, j + 2), recurse on (i + 2, j + 3)…循环的终止条件是p[i]和s[j]不match了，直接返回false。

public boolean isMatch(String s, String p) {
  return tryMatch(p, s, 0, 0);
}
private boolean tryMatch(String p, String s, int i, int j) {
  if (i == p.length())
    return j == s.length();
  if (i == p.length() - 1 || p.charAt(i + 1) != '*') { //下一个字母不是*，当前字母必须match
    if (matchChar(p, s, i, j))
      return tryMatch(p, s, i + 1, j + 1);
    else
      return false;
  } else { // p[i + 1] is *
    boolean skip = tryMatch(p, s, i + 2, j); //把当前字母去掉能行，就直接返回
    if (skip)
      return true;
    while (matchChar(p, s, i, j)) {//*当一个p[i]开始，当两个，当三个。。
      if (tryMatch(p, s, i + 2, j + 1))
        return true;
      j++;
    }
    return false;
  }
}
private boolean matchChar(String p, String s, int i, int j) {
  if (i >= p.length() || j >= s.length())
    return false;
  return p.charAt(i) == s.charAt(j) || p.charAt(i) == '.';
}

Tags: dfs, hard, string