Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Recursive function to match a string against a wildcard pattern

So I've been trying to solve this assignment whole day, just can't get it.

The following function accepts 2 strings, the 2nd (not 1st) possibly containing *'s (asterisks).
An * is a replacement for a string (empty, 1 char or more), it can appear appear (only in s2) once, twice, more or not at all, it cannot be adjacent to another * (ab**c), no need to check that.

public static boolean samePattern(String s1, String s2)

It returns true if strings are of the same pattern.
It must be recursive, not use any loops, static & global variables. Can use local variables & method overloading.

Can use only these methods: charAt(i), substring(i), substring(i, j), length().

Examples:

1: TheExamIsEasy; 2: The*xamIs*y → true
1: TheExamIsEasy; 2: Th*mIsEasy* → true
1: TheExamIsEasy; 2: * → true
1: TheExamIsEasy; 2: TheExamIsEasy → true
1: TheExamIsEasy; 2: The*IsHard → FALSE

I tried comparing the the chars one by one using charAt until an asterisk is encountered, then check if the asterisk is an empty one by comparing is successive char (i+1) with the char of s1 at position i, if true -- continue recursion with i+1 as counter for s2 & i as counter for s1;
if false -- continue recursion with i+1 as counters for both.
Continue this until another asterisk is found or end of string.

I dunno, my brain loses track of things, can't concentrate, any pointers / hints? Am I in the right direction?

Also, it's been told that a backtracking technique is to be used to solve this.

My code so far (doesn't do the job, even theoretically):

public static boolean samePattern(String s1, String s2) {
    if (s1.equals(s2) || s2 == "*") {
        return true;
    }
    return samePattern(s1, s2, 1);
}
public static boolean samePattern(String s1, String s2, int i)
{
    if (s1.equals(s2))
        return true;
    if (i == s2.length() - 1) // No *'s found -- not same pattern.
        return false;

    if (s1.substring(0, i).equals(s2.substring(0, i)))
        samePattern(s1, s2, i+1);
    else if (s2.charAt(i-1) == '*')
        samePattern(s1.substring(0, i-1), s2.substring(0, i), 1); // new smaller strings.
    else
        samePattern(s1.substring(1), s2, i);
}
like image 883
George Kagan Avatar asked Jun 06 '10 20:06

George Kagan


People also ask

Which operator can be used to match string containing wildcard characters?

Use a wildcard to match any number of characters"*ed" matches a string of any length ending with "ed", such as "Ted" or "Treed".

Which wildcards are used for pattern matching?

Use the asterisk ( * ) to match any sequence or string of characters. The ( * ) indicates any characters, including no characters.

What is the pattern matching the wildcard in Unix?

The wildcard characters are asterisk ( * ) and question mark ( ? ). The metacharacters are open and close square brackets ( [ ] ), hyphen ( - ), and exclamation mark ( ! ). Use the asterisk ( * ) to match any sequence or string of characters. Use the ? to match any one character.


2 Answers

Here is how I solved it...

public static void main(String[] args)
{
    System.out.println(samePattern("TheExamIsEasy", "The*xamIs*y")); // True
    System.out.println(samePattern("TheExamIsEasy", "Th*mIsEasy*")); // True
    System.out.println(samePattern("TheExamIsEasy", "*")); // True
    System.out.println(samePattern("TheExamIsEasy", "TheExamIsEasy")); // True
    System.out.println(samePattern("TheExamIsEasy", "The*IsHard")); // false
}

public static boolean samePattern(String s1, String s2)
{
    if (s1.length() == 0 && s2.length() == 0 || 
            s1.length() == 0 && s2.length() == 1 && s2.charAt(0) == '*')
        return true;
    
    if (s1.length() == 0 || s2.length() == 0)
        return false;           
    
    if (s1.charAt(0) == s2.charAt(0))
        return samePattern(s1.substring(1), s2.substring(1));
    
    boolean r1 = samePattern(s1, s2.substring(1));
    boolean r2 = samePattern(s1.substring(1), s2);
    
    return r1 || r2;
}
like image 187
AshesAndDust Avatar answered Sep 29 '22 19:09

AshesAndDust


Here's some Python "psudocode" that may help

def samePattern(s1,s2):
    if s2 == "*" or s1 == s2: return True
    if s1 == "": return False
    if s1[0] == s2[0]: return samePattern(s1[1:], s2[1:])
    if s2[0] == "*": return samePattern(s1, s2[1:]) or samePattern(s1[1:], s2)
    return False

Here is a rough guide for converting the code

s[0] = the first character
s[1:] = the string minus the first character
like image 43
John La Rooy Avatar answered Sep 29 '22 17:09

John La Rooy