面试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"));
}
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 面试10大算法题汇总-字符串和数组4

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡