Java：通配符模式匹配

Question

我一直在尝试解决通配符模式匹配问题，我在下面找到了一个可行的解决方案 link:

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

我已经为上面link中给出的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

:)

首先我注意到代码 && (format.length() != 0 && 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.length() != 0，因此该条件始终为假，因为长度不能同时为 0 和非 0。

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

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; }

Java：通配符模式匹配

Java: Wildcard Pattern Matching

java

wildcard

pattern-matching