Java:通配符模式匹配

Question

我一直在尝试解决通配符模式匹配问题，并在以下链接中找到了一个有效的解决方案：

http://www.geeksforgeeks.org/wildcard-character-matching/

我已经为上面链接中给出的C代码编写了一个等效的java代码，它是：

    public class wildcard
{
    public static void main(String[] args) 
    {
        test("g*ks", "geeks"); 
        //test("g*k", "gee"); 
        //test("c*d*", "cad");
}
static boolean matches(String format, String data)
{

    if (format.length() == 0 && data.length() == 0)
    {
        return true;
    }
    if ((format.charAt(0) == '*' && format.charAt(1) != 0 && data.length() == 0) && (format.length() != 0 && data.length() != 0))
    {
        return false;
    }
    if ((format.charAt(0) == '?' || format.charAt(0)  == data.charAt(0)) && (format.length() != 0 && data.length() != 0))
    {
        return matches(format.substring(1), data.substring(1));
    }
    if ((format.charAt(0) == '*')&& (format.length() != 0 && data.length() != 0))
    {
        return matches(format.substring(1), data) || matches(format, data.substring(1));
    }

    return false;
}
static void test(String first, String second)
{ 
    System.out.println(matches(first, second)); 
}
}

在执行时，抛出一个字符串越界异常，它是：

    Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 1
at java.lang.String.charAt(String.java:658)
at wildcard.matches(wildcard.java:29)
at wildcard.matches(wildcard.java:36)
at wildcard.matches(wildcard.java:42)
at wildcard.matches(wildcard.java:42)
at wildcard.matches(wildcard.java:36)
at wildcard.test(wildcard.java:52)
at wildcard.main(wildcard.java:16)

我可以看到这个异常发生在CharAt（）方法上，有其他方法可以实现吗？？

Answer 1

：）

首先，我注意到代码&amp；（format.length（）！=0&amp；data.length（）！=0）不在您提供的页面的原始代码中，并且导致与您的算法发生冲突，因此我将其删除，看起来如下：

static boolean matches(String format, String data) {
    if (format.length() == 0 && data.length() == 0) {
        return true;
    }
    if (format.charAt(0) == '*' && format.charAt(1) != 0 && data.length() == 0) {
        return false;
    }
    if (format.charAt(0) == '?' || format.charAt(0) == data.charAt(0)) {
        return matches(format.substring(1), data.substring(1));
    }
    if (format.charAt(0) == '*') {
        return matches(format.substring(1), data) || matches(format, data.substring(1));
    }
    return false;
}

我谈到的问题是在第二个条件中，您有data.length（）==0，而在我删除的代码中是data.lenght（）！=0，因此该条件始终为false，因为长度不能同时为0而不是0。

我发现了两个问题。第一种情况是，像matches("ge?ks*", "geeksforgeeks")这样的一些情况最终在格式上有一个通配符，并且由于格式而在if (format.charAt(0) == '*' && format.charAt(1) != 0 && data.length() == 0)上崩溃。charAt（1）。为了解决这个问题，我在算法中添加了下一个代码：

if (format.length() == 1 && format.charAt(0) == '*')
        return true;

另一个问题是当格式为空但仍有数据并使用解决时

if (format.length() == 0 && data.length() > 0)
        return false;

最后的算法是这样的：

static boolean matches(String format, String data) {
    if (format.length() == 0 && data.length() == 0)
        return true;
    if (format.length() == 1 && format.charAt(0) == '*')
        return true;
    if (format.length() == 0 && data.length() > 0)
        return false;
    if (format.charAt(0) == '*' && format.charAt(1) != 0 && data.length() == 0)
        return false;
    if (format.charAt(0) == '?' || format.charAt(0) == data.charAt(0))
        return matches(format.substring(1), data.substring(1));
    if (format.charAt(0) == '*')
        return matches(format.substring(1), data) || matches(format, data.substring(1));
    return false;
}