Recursion problem; completely lost
- by timeNomad
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);
}
