Leetcode P44 java一次遍历

Leetcode P44 java一次遍历

执行用时：2 ms, 在所有 Java 提交中击败了93.75%的用户

内存消耗：41.2 MB, 在所有 Java 提交中击败了99.19%的用户

通过测试用例：1811 / 1811

idea

首先我们创建一些变量

        int sp = 0; //s的指针
        int pp = 0; //p的指针
        int matchIndex =-1; //s字符串当前与*匹配的下标
        int starIndex  =-1;  //p字符串*出现的下标
1
2
3
4

接下来拿s字符串与p进行匹配

       while (sp < s.length()) {
            ....
        }
1
2
3

在匹配的过程中会发生几种情况

如果当前sp和pp下标的字符是一致，或者sp与pp下标的字符不一致但是pp下标字符是? 那么我们直接指针下移就好了

            //如果单个字符匹配成功或者与？匹配成功
            if (pp < p.length() && (p.charAt(pp) == s.charAt(sp) || p.charAt(pp) == '?')){
                sp++;
                pp++;
            }
1
2
3
4
5

如果我们pp下标的元素是*那么就我们记录下星的位置，还有s字符串中开始匹配的下标，如果已经记录过一次星星了在出现了一次星星那么就记录新的星星的下标

//如果当前是* 进行标记
else if (pp < p.length() && p.charAt(pp) == '*') {
    starIndex  = pp;
    matchIndex = sp;
    pp++;
}
1
2
3
4
5
6

如果我们出现了匹配不上的字符，但是我们已经记录过*了，那么我们假sp,matchIndex区间的字符都被⭐所替换了，在将p字符串的指针移动到星星所在的下标，

//某个字符需要用到此*进行匹配
else if (starIndex != -1) {
    pp = starIndex; //将pp移动到*的位置
    matchIndex++;   //匹配下标移动
    sp = matchIndex; //查看匹配下标是否能与pp进行匹配
}
1
2
3
4
5
6

如果以上判定都不满足，那么一定无法匹配返回false

else {
    return false;
}
1
2
3

这时候我们s字符串匹配完毕了，但是我们p字符串可能还有内容如果剩下的内容都是⭐那么我们就判定为匹配成功，如果不是⭐那么就匹配失败，因为s中没有字符再让p去匹配了

        while(pp < p.length() && p.charAt(pp) == '*'){
            pp++;
        }

        return pp == p.length();
1
2
3
4
5

code

public boolean isMatch(String s, String p) {
    int sp = 0; //s的指针
    int pp = 0; //p的指针
    int matchIndex =-1; //s字符串当前与*匹配的下标
    int starIndex  =-1;  //p字符串*出现的下标
    //s与p进行匹配
    while (sp < s.length()) {
        //如果单个字符匹配成功或者与？匹配成功
        if (pp < p.length() && (p.charAt(pp) == s.charAt(sp) || p.charAt(pp) == '?')){
            sp++;
            pp++;
        }
        //如果当前是* 进行标记
        else if (pp < p.length() && p.charAt(pp) == '*') {
            starIndex  = pp;
            matchIndex = sp;
            pp++;
        }
        //某个字符需要用到此*进行匹配
        else if (starIndex != -1) {
            pp = starIndex; //将pp移动到*的位置
            matchIndex++;   //匹配下标移动
            sp = matchIndex; //查看匹配下标是否能与pp进行匹配
        }else {
            return false;
        }
    }

    while(pp < p.length() && p.charAt(pp) == '*'){
        pp++;
    }

    return pp == p.length();
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34