Lexi's Leetcode solutions

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

Posted on: August 25, 2013

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) == '.';
}
Advertisements
Tags: , ,

1 Response to "[leetcode] Regular Expression Matching | 看string a是否match regex b"

双指针感觉好难理解,但是很精妙啊。

背后的原理是一个确定有限状态机

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: