Recursion problem; completely lost

Question

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

Answer 1

Here is sample solution written in c#. Sorry for lack of comments but I didn't have time for them :/ If you will still need them tomorrow then I can write some, but I hope You will grab the idea.

 public static bool CompareString(string s1, string s2, bool wildCard)
 {
        // Both strings are empty
        if ((s1.Length == 0) && (s2.Length == 0)) return true;

        // Second string is empty and there is wildCard character
        if (s2.Length == 0 && wildCard) return true;

        //First string is empty. Answer will be true only if all characters in second string are *.
        if (s1.Length == 0 && s2.Length > 0 && s2[0] == '*')
        {
            string newS2 = s2.Remove(0, 1);
            return CompareString(s1, newS2, true);
        }

        // One of the strings is empty, and second one is not.
        if (s1.Length * s2.Length == 0) return false;

        if (wildCard)
        {
            string newS1 = s1.Remove(0, 1);
            if (CompareString(newS1,s2,true) || CompareString(newS1,s2,false))
            {
                return true;
            }
        }
        else
        {
            if (s2[0] == '*')
            {
                string newS2 = s2.Remove(0,1);
                if (CompareString(s1,newS2,true) || CompareString(s1,newS2,false))
                {
                    return true;
                }
            }
            else
            {
                if (s1[0] == s2[0])
                {
                    string newS1 = s1.Remove(0,1);
                    string newS2 = s2.Remove(0,1);
                    return CompareString(newS1,newS2,false);
                }
                else
                {
                    return false;
                }
            }
        }
        return false;
    }

Answer 2

The problem with your current approach is that it doesn't consider all the possible substrings that a * can match. For example, samePattern("ababababab", "a*b") should return true; the * can match all but the first and last letter of the string, but your code assumes that since the following letter is b, the * matches the empty string.

I suggest thinking of samePattern as "consuming" its two input strings as it looks for a match. At each step, samePattern should only need to look at the first character of each string to decide whether a match at the first character is possible, and if so make a recursive call to check the rest of the string. The trick will be knowing what to do when you reach a * in the pattern string, since it may or may not be used to match the first character in s1. You shouldn't need to look at the rest of the string to decide what to do.

Since this is homework, I'll leave figuring out the details of what happens there to you, but hopefully this gets you thinking down the right path.

Answer 3

When dealing with algorithms like this, it often pays to break the problem into small chunks in your head.

Since you're string parsing, consider the solution on a character-by-character basis. Furthermore, since you have no control over the actual size of these strings, constrain yourself to considering only the first character of the string at any given time. (well - with one exception)

Once you've determined that the characters you're dealing with warrant further investigation into the rest of the string, toss them away; keeping them around only adds complexity, so why bother? (Conversely, if the characters flat out mismatch, you're done - right?)

Of course, this is a recursion on strings, so you'll have to have a couple of conditions governing failure/success that deal with the overall state of the strings - but those aren't the meat of the problem - check the state of the string at the top of your function, and move on.

I have an algorithm that I whipped up (11 lines of code, plus braces) that I can post if you want a full solution - but I wasn't sure by your message if you wanted to be given the algorithm, or just pointers.

Answer 4

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[1:],s2) or samePattern(s1,s2[1:])
    return False

Here is a rough guide for converting the code

s[0] = the first character
s[1:] = the string minus the first character