0

我有一个家庭作业，我就是想不通。我必须编写一个静态方法 match(String x, String y)，它返回一个布尔值来判断字符串 x 和字符串 y 是否匹配。匹配过程应允许“通配符”，例如将匹配任何单个字符的“@”字符和将匹配任何类型的 0 个或多个字符的“*”字符。我不允许使用任何循环，我必须使用递归。到目前为止，我写的就是这个……

public class CompareStrings {
public static boolean match(String x, String y) {
    if (x.length() <= 1 && y.length() <= 1) {
        if (x.equals("*") || y.equals("*")) {
            return true;
        }
        if ((x.length() == 1 && y.length() == 1) && (x.equals("@") || y.equals("@"))) {
            return true;
        }
        return  x.equals(y);
    }
    String x1 = "";
    String x2 = "";
    String y1 = "";
    String y2 = "";
    if (x.length() == 0 && y.charAt(0) == '*') {
            y2 = y.substring(1, y.length());
    }
    if (y.length() == 0 && x.charAt(0) == '*') {
            x2 = x.substring(1, x.length());
    }
    if (x.length() > 1 && y.length() > 1) {
        if (x.length() != y.length() && !x.contains("*") && !y.contains("*")) {
            return false;
        }
        if (x.charAt(0) == '*') {
            x1 = "*";
            x2 = x.substring(1, x.length());
            y1 = "*";
            y2 = y.substring(y.length()-x2.length(), y.length());
        }
        else if (y.charAt(0) == '*') {
            y1 = "*";
            y2 = y.substring(1, y.length());
            x1 = "*";
            x2 = x.substring(x.length()-y2.length(), x.length());
        }
        else {
            x1 = x.substring(0, 1);
            x2 = x.substring(1, x.length());
            y1 = y.substring(0, 1);
            y2 = y.substring(1, y.length());
        }
    }
    return match(x1, y1) && match(x2, y2);
}

public static void main(String[] args) {
    System.out.println(match("hello", "hello.") + " 1 false"); // should return false
    System.out.println(match("hello", "jello") + " 2 false"); // should return false
    System.out.println(match("hello", "h@llo") + " 3 true"); // should return true
    System.out.println(match("hello", "h@@@@") + " 4 true"); // should return true
    System.out.println(match("hello", "h*") + " 5 true"); // should return true
    System.out.println(match("hello", "*l*") + " 6 true"); // should return true
    System.out.println(match("anyString", "*") + " 7 true"); // should return true
    System.out.println(match("help", "h@@@@") + " 8 false"); // should return false
    System.out.println(match("help", "h*") + " 9 true"); // should return true
    System.out.println(match("help", "*l*") + " 10 true"); // should return true
    System.out.println(match("help", "*l*p") + " 11 true"); // should return true
    System.out.println(match("help", "h@llo") + " 12 false"); // should return false
    System.out.println(match("", "*") + " 13 true"); // should return true
    System.out.println(match("", "***") + " 14 true"); // should return true
    System.out.println(match("", "@") + " 15 false"); // should return false
    System.out.println(match("", "") + " 16 true"); // should return true
}

}

主要方法是作业给出的测试程序。我意识到我的代码有点乱——我有点乱——但我似乎可以让它大部分工作。唯一没有返回正确值的例子是数字 11。当它应该为真时，我得到了假。我认为发生这种情况的原因是因为字符串 y 以 ' ' 开头，我的方法所做的就是将 x 和 y 字符串拆分为最后 3 个字符，即使y 中的第一个 ' ' 应该代表 2人物。我怎样才能使这样的情况返回匹配项？

4

2 回答 2

1

基本上你需要了解递归的概念（这是你作业的目标）。递归的工作方式是每次函数调用自身时，当前执行（变量/执行信息）都会进入堆栈并在那里休眠，直到新调用完成。

为了解决您提到的问题，让我们举一个简单的例子，hello 和 h@llo。解决问题的一个基本方法是匹配服务一次又一次地调用自己，直到

  1. 找到完美匹配 - 返回 true

  2. 发现失败条件 - 返回 false

  3. 在没有上述 2 的情况下，match 调用自身，其字符比 prev 调用少一个字符

就像是

调用 1: hello & h@llo// 调用再次匹配，当前调用移动到堆栈，等待回复

调用 2: ello & @llo //匹配特殊字符

call 3: llo 和 llo// 完美匹配返回 true 来调用 2

返回调用 2：从 prv 调用接收 true 并返回调用 1

返回调用1：接收true并返回main。

一旦你理解了递归栈的概念，解决这个问题就会很简单

您的最终匹配方法将类似于 

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

    //if both are empty
    if(x.length()==0 && y.length()==0) return true;

    //if one is empty
    if(x.length()==0 )
    {
        if(y.charAt(0)!='*')
            return false;
        if(y.length()!=1)
            //border line case
            return match(x,y.substring(1));
        else 
            return true;
    }
    if(y.length()==0 )
    {
        if(x.charAt(0)!='*')
            return false;
        if(x.length()!=1)
            //border line case
            return match(y,x.substring(1));
        else 
            return true;
    }   

    //Base case 
    if(x.equals(y) || x.equals("*") || y.equals("*"))
    {

        return true;//we are done as strings are equal
    }


    //we are here that means strings are not equal yet 
    if(x.charAt(0)=='@' || y.charAt(0)=='@' ||x.charAt(0)==y.charAt(0))
    {
        if(x.length()==1 && y.length()==1) return true;//this was the last character
        if(x.length()>1 && y.length()>1)
        {

            //we have single char wild card or char 0 equal,  lets remove the char at 0th location and check again 
            return (match(x.substring(1),y.substring(1)));
        }
    }

    if(x.charAt(0)=='*')
    {
        //this is interesting now, we will need to skip 0..n number of characters till we find matching pattern
        //case 0 chars: he*llo and hello
        if(match(x.substring(1),y)==true)
            {
                return true;
            }
        else if (match(x.substring(1),y.substring(1))==true)
        {
            //case 1: he*lo and hello
            return true;
        }           
        else
        {
            //case n chars: h*o and hello
            return (match(x, y.substring(1)));
        }

    }

    if(y.charAt(0)=='*')
    {
        //this is interesting now, we will need to skip 0..n number of characters till we find matching pattern
        //case 0 chars: he*llo and hello
        if(match(y.substring(1),x)==true)
            {
                return true;
            }
        else if (match(x.substring(1),y.substring(1))==true)
        {
            //case 1: he*lo and hello
            return true;
        }           
        else
        {
            //case n chars: h*o and hello
            return (match(y, x.substring(1)));
        }

    }
    //nothing worked out
    return false;
}
于 2013-04-05T06:08:20.650 回答
0

本着recursion（你的标签之一）但不是 Java 的精神，这里有一个 Scheme 实现，它可以让你的所有测试用例都正确。

(define (match s1 s2) ; assumes s1 = string, s2 = pattern
  (let matching ((l1 (string->list s1)) (l2 (string->list s2)))
    (if (null? l1)
        (or (null? l2) (eq? (car l2) #\*)) ; every #\*
        (let ((c1 (car l1))
              (c2 (car l2)))
          (or (and (or (eq? c2 c1)
                       (eq? c2 #\@))
                   (matching (cdr l1) (cdr l2))) ; take one char from l1 and l2
              (and (eq? c2 #\*)
                   (matching (cdr l1) l2)))))))  ; take one char from l1

请注意，对于具有上述内容的测试用例"*l*"，得到了正确的答案，但原因是错误的。上面还有其他错误（与 相关"*"），但不在您的测试用例中。

于 2013-04-05T05:50:40.407 回答