Compare strings using recursion

Question

I've got a homework assignment that I just can't figure out. I have to write a static method match(String x, String y) that returns a boolean for whether or not string x and string y match. The matching process should allow "wild cards" such as '@' character which will match with any single character and the '*' character which will match with 0 or more characters of any type. I'm not allowed to use any loops and I have to use recursion. What I've written so far is this...

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
}

}

The main method is the test program given by the assignment. I realize my code is a little messy - I was scrambling a bit - but I can seem to get most of it working. The only example that doesn't return the right value is number 11. I get false when it should be true. The reason I think this is happening is because since the string y starts with a '', the thing my method does is splits both x and y strings into their last 3 characters, even though that first '' in y is supposed to represent 2 characters. How can I make it so that cases like this return a match?

Answer 1

Basically you need to understand the concept of recursion (that is the objective of your homework). The way recursion works is that everytime a function calls itself, the current execution (variables/ execution info) goes onto a stack and sleeps there till the new call finishes.

To solve the problem you have mentioned, lets take a simple example, hello and h@llo. A basic way to solve problem will be that match service call itself again and again till

1. A perfect match is found - return true

2. A failure condition is found- return false

3. In absence of above 2, match calls itself with one character less than the prev call

Something like

Call 1: hello & h@llo// calls match again and present call moves to stack, waits for a reply

Call 2: ello & @llo //matches special character

call 3: llo and llo// perfect match return true to call 2

Back to call 2: receives true from prv call and returns back to call 1

Back to call 1: receives true and returns to main.

Once you understand the concept of recursion stack, solving this problem will be simple

Your final match method will look something like

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

Answer 2

In the spirit of recursion (one of your tags) but not of Java, here is a Scheme implementation that gets all your test cases correct.

(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

Note, for test cases with "*l*" the above gets the right answer but for the wrong reason. There are others that the above gets wrong (related to "*") but that are not in your test cases.