Java Recursive String Comparison with "*" as a Wildcard

Question

I'm writing a recursive method that checks each letter of the string to compare them. I'm having trouble making the "*" character match with any, and act as as many letters as needed. (Making it a wildcard)

I was wondering if someone can give me a hint on the algorithm that would be used?

Here is what I have so far.

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
}

What I was thinking of doing is adding another arguement to the method, an int that will act as a letter backcounter. Basically I'm thinking of this if a or b at char(i-s) (s originally being 1.) is a *, recall the recursion with s+1. and then a few more different ifs statements to fix the bugs. However this method seems really long and repetitive. Are there any other algorithms I can use?

Can wildcards appear in both strings, or only one? If one, which one? — Bohemian, Apr 03 '13 at 06:19
Is there any particular reason why you are solving this using recursion? This kind of pattern-matching is typically solved using a state machine. http://en.wikipedia.org/wiki/Finite-state_machine In your example you will run into the scenario where the star match "est", and thus nothing is left of the a-string to match the final "t" in the b-string. Your algorithm must handle these scenarios. (Seach for "non greedy regexp" for more info) — Rolf Rander, Apr 03 '13 at 06:23
Class assignment on recursion. Thank you, will read up on that — user1692517, Apr 03 '13 at 06:26

score 2 · Answer 1 · answered Apr 03 '13 at 06:12

2

Do not use == for String value comparison. Use the equals() method.

if (a == b) should be if a.equals(b)

answered Apr 03 '13 at 06:12

Rahul

44,383
11
84
103

Thank you, is there a reason why? == works too, or is it one of those unnamed java rules – user1692517 Apr 03 '13 at 06:14
@user1692517 see http://stackoverflow.com/questions/767372/java-string-equals-versus – Justin Apr 03 '13 at 06:15
a==b returns true if a and b are the same object. a.equals(b) return true if they are different objects but with the same content. – Rolf Rander Apr 03 '13 at 06:16
@user1692517 you need to read this http://stackoverflow.com/questions/513832/how-do-i-compare-strings-in-java – Ankit Apr 03 '13 at 06:17

score 1 · Answer 2 · answered Jan 06 '15 at 11:29

If you are using only one character("*") as a wildcard, I recommend you to use regular expression. Such as;

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
}

I think it is easier to read the code this way.

score 0 · Answer 3 · answered Apr 03 '13 at 06:36

0

Have a look at this algorithm. It returns all substrings that match the pattern, so you'll have to check whether the entire string is matched in the end, but that should be easy.

It runs in O(km) time, where k is the number of wildcards and m is the length of your input string.

answered Apr 03 '13 at 06:36

Vincent van der Weele

12,927
1
33
61

The algorithm by the link is strange as regards '*' as one symbol not zero or many. – bitec Jan 04 '15 at 19:36

Anders Johansen · Answer 4 · 2013-04-03T06:27:37.317

This book will tell you exactly how to do it: http://www.amazon.com/Compilers-Principles-Techniques-Alfred-Aho/dp/0201100886

Here's a simple Java implementation that might get you on track: http://matt.might.net/articles/implementation-of-nfas-and-regular-expressions-in-java/

Basically the industrial-strength implementation is a state machine. You deconstruct the regular expression - the string with the '*' in it - and create a graph for it. Then you recursively search the graph, for example in a breadth-first tree search.

Here's some discussion of different ways to do it, that will help illustrate the approach: http://swtch.com/~rsc/regexp/regexp1.html

Java Recursive String Comparison with "*" as a Wildcard

4 Answers4

Linked