0

どうしても分からない宿題があります。文字列 x と文字列 y が一致するかどうかのブール値を返す静的メソッド match(String x, String y) を作成する必要があります。マッチング プロセスでは、任意の 1 文字と一致する「@」文字や、任意のタイプの 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 番です。true であるべきときに false になります。これが起こっていると思う理由は、文字列 y が ' ' で始まるため、 y の最初の ' ' が 2 を表すはずなのに、私のメソッドが x と y の両方の文字列を最後の 3 文字に分割するためです。文字。このようなケースが一致を返すようにするにはどうすればよいですか?

4

2 に答える 2

1

基本的に、再帰の概念を理解する必要があります (それが宿題の目的です)。再帰が機能する方法は、関数がそれ自体を呼び出すたびに、現在の実行 (変数/実行情報) がスタックに移動し、新しい呼び出しが完了するまでそこでスリープすることです。

あなたが言及した問題を解決するために、簡単な例、hello と h@llo を見てみましょう。問題を解決する基本的な方法は、一致するサービス自体を何度も何度も呼び出すことです。

  1. 完全一致が見つかった - true を返す

  2. 失敗条件が見つかった - false を返す

  3. 上記の 2 がない場合、match は前の呼び出しよりも 1 文字少ない文字でそれ自体を呼び出します

何かのようなもの

呼び出し 1: hello & h@llo// 呼び出しが再び一致し、現在の呼び出しがスタックに移動し、応答を待ちます

Call 2: ello & @llo //特殊文字に一致

呼び出し 3: llo と llo// 完全一致は true を呼び出し 2 に返します

呼び出し 2 に戻る: prv 呼び出しから true を受け取り、呼び出し 1 に戻ります。

コール 1 に戻る: true を受け取り、メインに戻ります。

再帰スタックの概念を理解すれば、この問題は簡単に解決できます

最終的な一致方法は次のようになります 

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

recursionJava ではなく (タグの 1 つ)の精神で、すべてのテスト ケースを正しく取得する 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 に答える