CODEWITHSUNDEEP
javaequals
user360256
user360256

Reputation: 1

Help with string equality in Java

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.

Upvotes: 1

Views: 681

Answers (2)

polygenelubricants
polygenelubricants

Reputation: 384006

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

Upvotes: 2

Eric
Eric

Reputation: 97681

Looks like you might want regular expressions.

The .+ regex pattern is equivalent to your *.

But then you'd have two problems.

Upvotes: 5

Related Questions