6.匹配正则表达式
编写函数boolisMatch(String s, String p)，完成正则表达式中“.”和“*”的功能。例：
isMatch("aa","a")return false
isMatch("aa","aa")return true
isMatch("aaa","aa")return false
isMatch("aa", "a*")return true
isMatch("aa", ".*")return true
isMatch("ab", ".*")return true
isMatch("aab", "c*a*b")return true
注：p的第1个字符不为*，且p中不会出现两个*连接在1起的情况
可将问题分为以下几种情况斟酌：
1. p的长度为0：此时s的长度必须为0才匹配
2. p的长度为1：若s的长度小于1，则必定不匹配。否则若p.charAt(0)不为“.”或与s不相等则不匹配
3. p的长度>1：
此处罚两种可能斟酌：I.p.charAt(1) != ‘*’
II.p.charAt(1) == ‘*
当p.charAt(1) != ‘*’时，若s的长度小于1，则必定不匹配。比较s与p的第1个字符是不是匹配：若s与p的第1个字符不同且p的第1个字符不为”.”，则不匹配。否则迭代调用函数，返回isMatch(s.substring(1),p.substring(1))
当p.charAt(1) == ‘*’时，
。。。
PS:代码有问题：
http://www.programcreek.com/2012/12/leetcode-regular-expression-matching-in-java/
比以下面代码的测试就失败了，暂时没想到解决方法：
public static boolean isMatch(String s, String p) {
// base case
if (p.length() == 0) {
return s.length() == 0;
}
// special case
if (p.length() == 1) {
// if the length of s is 0, return false
if (s.length() < 1) {
return false;
}
//if the first does not match, return false
else if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) {
return false;
}
// otherwise, compare the rest of the string of s and p.
else {
return isMatch(s.substring(1), p.substring(1));
}
}
// case 1: when the second char of p is not '*'
if (p.charAt(1) != '*') {
if (s.length() < 1) {
return false;
}
if ((p.charAt(0) != s.charAt(0)) && (p.charAt(0) != '.')) {
return false;
} else {
return isMatch(s.substring(1), p.substring(1));
}
}
// case 2: when the second char of p is '*', complex case.
else {
//case 2.1: a char & '*' can stand for 0 element
if (isMatch(s, p.substring(2))) {
return true;
}
//case 2.2: a char & '*' can stand for 1 or more preceding element,
//so try every sub string
int i = 0;
while (i<s.length() && (s.charAt(i)==p.charAt(0) || p.charAt(0)=='.')){
if (isMatch(s.substring(i + 1), p.substring(2))) {
return true;
}
i++;
}
return false;
}
}
public static void main(String[] args) {
System.out.println(isMatch("12", "1*12"));
}
}
波比源码 » 面试10大算法题汇总-字符串和数组4
