0

我正在编写一个递归方法来检查字符串的每个字母以比较它们。我无法使“*”字符与任何字符匹配，并根据需要充当尽可能多的字母。（使其成为通配符）

我想知道是否有人可以给我一个关于将使用的算法的提示？

这是我到目前为止所拥有的。

public static boolean match(String x, String y) {
    return match_loop(x, y, 0, 1);
}

public static boolean match_loop(String a, String b, int i, int s) {
    try {
        if (a == b) {
            return true;
        }

        if (i >= a.length() && i >= b.length()) {
            return true;
        }

        if (a.charAt(i) == b.charAt(i)) {
            return match_loop(a, b, i + 1, s);
        }


        //(((...A bunch of if statements for my other recursion requirements

        return false;

    } catch (java.lang.StringIndexOutOfBoundsException e) {
        return false;
    }
}

public static void main(String[] args) {
    System.out.println(match("test", "t*t")); // should return true
}

我想做的是在该方法中添加另一个参数，一个 int 将充当一个字母反向计数器。基本上，如果 char(is) 处的 a 或 b (s 最初为 1.) 是 *，我正在考虑这一点，回想一下 s+1 的递归。然后使用更多不同的 ifs 语句来修复错误。然而，这种方法似乎真的很长而且重复。我可以使用其他算法吗？

4

4 回答 4

2

不要==用于String价值比较。使用equals()方法。

if (a == b)应该if a.equals(b)

于 2013-04-03T06:12:51.263 回答
1

如果您只使用一个字符（“*”）作为通配符，我建议您使用正则表达式。如;

public static boolean match(String x, String y) {
    String regex= y.replace("*", "(.*)");
    if(x.matches(regex)) {
        return true;
    }
}


public static void main(String[] args) {
    System.out.println(match("test", "t*t")); // should return true
}

我认为以这种方式阅读代码更容易。

于 2015-01-06T11:29:59.453 回答
0

看看这个算法。它返回与模式匹配的所有子字符串，因此您必须检查整个字符串是否最终匹配，但这应该很容易。

它在 O(km) 时间内运行，其中 k 是通配符的数量，m 是输入字符串的长度。

于 2013-04-03T06:36:05.403 回答
-1

这本书将告诉您确切的操作方法： http: //www.amazon.com/Compilers-Principles-Techniques-Alfred-Aho/dp/0201100886

这是一个简单的 Java 实现，可能会让您走上正轨： http: //matt.might.net/articles/implementation-of-nfas-and-regular-expressions-in-java/

基本上工业级的实现是一个状态机。您解构正则表达式——其中带有“*”的字符串——并为它创建一个图形。然后递归搜索图形，例如在广度优先树搜索中。

以下是对不同方法的一些讨论，这将有助于说明该方法：http ://swtch.com/~rsc/regexp/regexp1.html

于 2013-04-03T06:21:11.523 回答