面试10大算法题汇总-字符串和数组4
|
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 class test {
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"));
}
}
（编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |