题目:Regular Expression Matching
Implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(const char *s,const char *p)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa","a") → true
isMatch("aa",".") → true
isMatch("ab",".") → true
isMatch("aab","cab") → true
分析:题目要求挺简单的,字符匹配,对.
和*
做特殊处理,字符串的匹配可以拆分成子串的匹配,子串的匹配又可归纳为每个字符的匹配,因此这道题用递归比较方便。
首先,抛开.
和*
不管,如何递归地判断两个字符串相等呢?
public class Solution { public boolean isMatch(String s,String p) { int slen = s.length(); int plen = p.length(); if (slen == 0 && plen == 0) return true; char c0 = getChar(s,0); char p0 = getChar(p,0); if (match(c0,p0)) { return isMatch(s.substring(1),p.substring(1)); } return false; } //判断两个字符是否相等 private boolean match(char a,char b) { return a == b; } //为什么要这个函数呢,主要是为了统一处理下标越界的问题 //如果越界了,直接返回0即可 private char getChar(String s,int p) { if (s.length() > p) { return s.charAt(p); } return 0; } }
根据题意,.
可根任何字符匹配,那么match
方法就要改成:
//判断两个字符是否相等 private boolean match(char a,char b) { return a == b || b == '.'; }
由于*
对前一个字符有副作用,故需要对*
进行特殊判断。尤其是[任意字符]*
可以匹配任意长度的字符串,包括空串。因此,每次处理isMatch
时,都要向后探一下接下来是否有*
:
- 如果有*,则枚举其匹配所有可能性,只要有一个返回true,则返回true
- 如果没有*,上述代码的逻辑则不需要变
最终代码:
public class Solution { public boolean isMatch(String s,0),p1 = getChar(p,1); if (match(c0,p0) || p1 == '*') { if (p1 != '*') { if (slen == 0) return false; return isMatch(s.substring(1),p.substring(1)); } // if p1 is *,* means 0 ~ n int i = 0; boolean ret = isMatch(s.substring(0),p.substring(2)); // try 0 if (ret) return ret; while (i < slen && match(getChar(s,i),p0)) { ret = isMatch(s.substring(i+1),p.substring(2)); // try for every available position if (ret) return ret; i++; } } return false; } private boolean match(char a,char b) { return a == b || b == '.'; } private char getChar(String s,int p) { if (s.length() > p) { return s.charAt(p); } return 0; } }