[leetcode] Regular Expression Matching | 看string a是否match regex b
Posted August 25, 2013
on:example: aabc matches c*a*b.
思路:
- 两个指针i, j,i指regular expression,j指真的string。
- 观察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]..
- 先试试“用0个p[i]“,即把p[i]和他后面的* skip掉。若recurse (i + 2, j)成功了,直接返回true,不成功,接着做第二步。
- 从“用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) == '.'; }
March 26, 2016 at 11:16 am
双指针感觉好难理解,但是很精妙啊。
背后的原理是一个确定有限状态机