java - 确定两个字符串是否匹配的递归方法。匹配过程应该允许“通配符”。一个“@”和一个“*”

Question

下面代码中的递归方法 match(String x, String y) 将确定两个字符串是否匹配。匹配过程应该允许“通配符”。'@' 字符将与任何其他单个字符匹配，'*' 字符将与任何类型的 0 个或多个字符匹配。

到目前为止，这就是我得到的：

public static boolean match(String x, String y) {

    int len = x.length() < y.length() ? x.length() : y.length();

    if (len == 0 && x.length() > 0)
        return false;
    else if (len == 0 && y.length() > 0)
        return true;

    for (int i = 0; i < len;)
    {
        int v1 = x.charAt(i);
        int v2 = y.charAt(i);

        if (v1 == v2)
            return match(x.substring(1, x.length()),
                             y.substring(1, y.length()));
        else
            return false;
    }

    return false; 

}

任何帮助或指导将不胜感激。更具体地说，我如何使用递归来实现通配符。

Answer 1

看看这个。第一个想法，可以改进。

public static boolean match(String regex, String input) {
    return match(regex.toCharArray(), input.toCharArray(), regex.length() - 1, input.length() - 1);
}

private static boolean match(char[] regex, char[] input, int regexPosition, int inputPosition) {
    if (regexPosition < 0 || inputPosition < 0) {
        return false;
    }
    if (regexPosition == 0 && inputPosition == 0) {
        return true;
    }
    if (regex[regexPosition] == input[inputPosition] || regex[regexPosition] == '@') {
        return match(regex, input, regexPosition - 1, inputPosition - 1);
    }
    if (regex[regexPosition] == '*') {
        if (regex[regexPosition - 1] == '@') {
            /* @* => @ matter of taste. Sure there are counter examples. */
            return match(regex, input, regexPosition - 2, inputPosition - 1);
        }
        final int newInputPosition = String.valueOf(input).lastIndexOf(regex[regexPosition - 1]);
        if (newInputPosition >= 0) {
            return match(regex, input, regexPosition - 1, newInputPosition);
        }
    }
    return false;
}