当前位置 : 主页 > 编程语言 > 其它开发 >

Leetcode10 Regular Expression Matching

来源:互联网 收集:自由互联 发布时间:2022-05-30
这道题的题意是,给出一个字符串s和匹配串P。判断两个串是否匹配。特殊的是p串中会有. 和 *。.表示可以代替任意字符,*则是可以重复前面的字符任意次(0次也可以) 大体上思路就

 

 

这道题的题意是,给出一个字符串s和匹配串P。判断两个串是否匹配。特殊的是p串中会有. 和 *。.表示可以代替任意字符,*则是可以重复前面的字符任意次(0次也可以)
大体上思路就是,对于p的一个*,比如说是a*,我们要搞明白这在s串中对应了究竟几个a。然后我们需要把匹配上的字符在原本的字符串中划掉,再跑身下的字符串,也就是递归。
这个思路是以*为基础。把*和前面一个字符在p中当作一个整体,看匹配的s中多少个对应前面的字符。


考虑到递归,就要考虑最终情况。
如果p为空,则S为空则true,s不为空则false。
如果p长度为1,那么只有s长度为1且和p这一位相同才返回true,否则false。
如果p长度不是1,那么分两种情况:
第一种,当前两位不是一个字符+*,那么就比较s和p最前面一位,如果一样就递归s、p个删去最前面一位的,不一样返回false。比如s是abc,p是acd,因为第一位一样,就接着比较bc和cd就好了。
第二种,p的前两位是一个字符+*。这种情况下,我们可以删去s前任意位p星号前的字符。比如说s是aaaaaab,p前两位是a*,那么s前面几个a都要删掉。
当然,删掉任意数量的a都需要枚举,比如会出现如下情况:s是aaaaab,p是a*aab,那么你不能看到a*就把a全删了,所以要递归删任何数量a的情况。
public class Le10 {
    public boolean isMatch(String s, String p) {
        if(p.isEmpty())  return s.isEmpty();//如果p为空,那么s必须是空的
        if(p.length()==1)  return s.length()==1 && (p.charAt(0)=='.' || p.charAt(0)==s.charAt(0));//第一位字符进行比较
        if(p.charAt(1)!='*'){
            if(s.isEmpty())  return false;
            else return (p.charAt(0)=='.' || p.charAt(0)==s.charAt(0)) && isMatch(s.substring(1),p.substring(1));
        }
        while(!s.isEmpty() && (p.charAt(0)=='.' || p.charAt(0)==s.charAt(0))){
            if(isMatch(s,p.substring(2)))  return true;
            s=s.substring(1);
        }
        return isMatch(s,p.substring(2));
    }
    public static void main(String[] args){
        Le10 test = new Le10();
        System.out.println(test.isMatch("aab","c*a*b"));
    }
}

 

 
 
上一篇:利用快慢指针寻找链表中间节点
下一篇:没有了
网友评论