java - Java:如何实现通配符匹配？

我正在研究如何在BST中找到与目标最接近的k值，并遇到了以下规则实现：
'?' 匹配任何单个字符。
“*”匹配任何字符序列（包括空序列）。
匹配应该覆盖整个输入字符串（而不是部分）。
功能原型应为：
bool isMatch（常量字符*s，常量字符*p）
一些例子：
ismatch（“a a”，“a”）→false
isMatch（“aa”，“aa”）？？正确
ismatch（“aaa”，“aa”）→false
ismatch（“aa”、“*”）→true
ismatch（“a a”，“a*”））→true
伊斯马特（“AB”和“？*“）→真
ismatch（“aab”，“cab”）→false
代码：

import java.util.*;

public class WildcardMatching {
    boolean isMatch(String s, String p) {
        int i=0, j=0;
        int ii=-1, jj=-1;

        while(i<s.length()) {
            if(j<p.length() && p.charAt(j)=='*') {
                ii=i;
                jj=j;
                j++;
            } else if(j<p.length() &&
                      (s.charAt(i) == p.charAt(j) ||
                       p.charAt(j) == '?')) {
                i++;
                j++;
            } else {
                if(jj==-1) return false;

                j=jj;
                i=ii+1;
            }
        }

        while(j<p.length() && p.charAt(j)=='*') j++;

        return j==p.length();
    }

    public static void main(String args[]) {
        String s = "aab";
        String p = "a*";

        WildcardMatching wcm = new WildcardMatching();
        System.out.println(wcm.isMatch(s, p));
    }
}

我的问题是，有两个附加索引ii和jj的原因是什么，为什么它们要用-1初始化？它们的目的是什么？用i和j遍历它就不够了吗？
在第一个if病例中ii=i;和jj=j;的目的是什么，在第三个if病例中i=ii+1;和j=jj;的目的是什么？
最后，在什么情况下您会遇到while(j<p.length() && p.charAt(j)=='*') j++;？
例句对理解非常有帮助。
提前谢谢你，我们将接受你的回答/赞成票。

最佳答案

看起来ii和jj用于处理与任何序列匹配的通配符“*”。它们对-1的初始化充当一个标志：它告诉我们是否遇到了不匹配的序列，并且当前没有计算“*”。我们可以一次一个地看你的例子。
注意i与参数s（原始字符串）相关，j与参数p（模式）相关。
isMatch("aa","a")：
这将返回false，因为在我们离开while循环之前，j<p.length()语句将失败，因为p（“a”）的长度只有1，而s（“aa”）的长度是2，所以我们将跳转到else块。这就是-1初始化的原因：由于我们从未在p中看到任何通配符，jj仍然是-1，这表示字符串不可能匹配，因此返回false。
isMatch("aa","aa")：
s和p是完全相同的，因此程序重复地计算else if块，没有问题，最后在i等于2时（长度“aa”）跳出while循环第二个while循环从不运行，因为j不小于p.length()-事实上，由于else if同时递增i和j，它们都等于2，并且2不小于“aa”的长度我们返回j == p.length()，其计算结果为2 == 2，并得到true。
isMatch("aaa","aa")：这一次失败的原因与第一次相同。也就是说，字符串的长度不同，我们从来没有碰到过通配符。
isMatch("aa","*")：这是它变得有趣的地方首先，我们将进入if块，因为我们在p中看到了“*”我们将ii和jj设置为0，并且仅增加j。在第二次迭代中，j<p.length()失败，所以我们跳到else块。jj不再是-1（它是0），因此我们将j重置为0并将i设置为0+1这基本上允许我们继续计算通配符，因为j只是被重置为jj，它保留了通配符的位置，并且ii告诉我们从原始字符串的哪里开始这个测试用例还解释了第二个while循环在某些情况下，我们的模式可能比原始字符串短得多，因此我们需要确保它与通配符匹配。例如，isMatch("aaaaaa","a**")应该返回true，但最后的返回语句是检查是否j == p.length()，询问是否检查了整个模式。通常我们会在第一个通配符处停止，因为它匹配任何内容，所以我们需要最终遍历模式的其余部分，并确保它只包含通配符。
从这里可以看出其他测试用例背后的逻辑。我希望这有帮助！

关于java - Java:如何实现通配符匹配？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/41112057/