Help with string equality in Java

Question

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 or global variables. Also it's prohibited to use the method equals in the String class. Can use local variables and 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 am stucked on this question for many hours now! I need the solution in Java please kindly help me.

Answer 1

Looks like you might want regular expressions.

The .+ regex pattern is equivalent to your *.

But then you'd have two problems.

Answer 2

The following is a recursive, no loop solution to your problem in Java:

static boolean samePattern(String s1, String s2) {
    return
        s2.isEmpty() ?
            s1.isEmpty()
            :
        s2.charAt(0) == '*' ?
            samePattern(s1, s2.substring(1))
            || (!s1.isEmpty() && samePattern(s1.substring(1), s2))
            :
        !s1.isEmpty() && s2.charAt(0) == s1.charAt(0) ?
            samePattern(s1.substring(1), s2.substring(1))
            :
        false;
}
public static void main(String[] args) {
    String[] patterns = {
        "The*xamIs*y",    // true
        "Th*mIsEasy*",    // true
        "*",              // true
        "TheExamIsEasy",  // true
        "The*IsHard",     // false
    };
    for (String pattern : patterns) {
        System.out.println(samePattern("TheExamIsEasy", pattern));
    }
}

---

The algorithm

Essentially here's the recursive definition:

• If s2 is empty, then it's samePattern if s1 is also empty
• Otherwise s2 is not empty
  • If it starts with *, then it's samePattern if
    • It's samePattern with the * removed
    • Or it's samePattern with a character removed from s1 (if there's one)
  • Otherwise it starts with a regular character
    • If it matches the first character s1, then check if it's samePattern for the rest of s1, s2
    • Otherwise it's not samePattern, so it's false

---

Simplified version

Here's the simplified version of the above algorithm:

static boolean samePatternSimplified(String s1, String s2) {
    if (s2.length() == 0) {
        return s1.length() == 0;
    } else if (s2.charAt(0) == '*') {
        return samePatternSimplified(s1, s2.substring(1))
           || (s1.length() != 0 && samePatternSimplified(s1.substring(1), s2));
    } else if (s1.length() != 0 && s2.charAt(0) == s1.charAt(0)) {
        return samePatternSimplified(s1.substring(1), s2.substring(1));
    } else {
        return false;
    }
}

API links

• String.isEmpty()
  • Returns true if, and only if, length() is 0.
• JLS 15.25 Conditional Operator ?:
  • This is the ?: operator used in the original solution
• Java Language Guide/The for-each loop
  • This is the for (String pattern : patterns) construct above