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.

• Andy E: Please edit your title to more appropriately summarise the body of the question.
• skaffman: Shouting "URGENT" in your subject is not helping your cause, you know.
• S.Lott: The tags should be [Homework] and [Java]. Not [Javadoc]. What have you tried? This is not "Do My Homework For Me.com"
• Marcelo Cantos: Wow, it's urgent! I'd better answer it quickly!! Have you tried writing it yourself? If so, post some code. People are more likely to answer homework questions if a) your title is more descriptive than, "I need help!" and b) you show some evidence that you've worked at it yourself.
• user360256: I am sorry. I am new here I just found this website today. I am stuck on this question and don't have any idea how to solve it or write a method that checks the equality of strings using recursion. I am totally lost please 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.

• user360256: What is .+? I don't know this symbol
• Eric: Within a regular expression, .+ means "one or more (+) of any character (.)".
• Martin Milan: Since the OP's * can be empty, the proper regex would actually be [code].*[/code] Annayena - Don't trouble yourself too much with regular expressions - you've been asked to solve the problem a particular way, so solve it that way. You might want to suggest to your tutor that regular expressions would have provided an effective alternate method of solving this problem without recursion - but learn about Regular Expressions first so you can justify your argument. There are plenty of tutorials on the internet...

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

• user360256: Thank you very much for assisting me. However, you used for loop and it's not allowed to use loops in this exercise. Also what's pattern : patterns? I didn't learn about it, so it's now allowed to use it either. Also I don't see the code of the method isEmpty? It's not allowed to use an existing method it's obligatory to write it.
• user360256: Oh, you wrote for in the main method. Ok. But what about the IsEmpty method? Can you please write it?
• user360256: My teacher said there are many "stop" conditions. Are you sure you checked all the possibilites?
• Andrei Fierbinteanu: you can replace s1.isEmpty() with s1.length() == 0
• polygenelubricants: @annayena: I'm not here to do your coursework. I'm here to show you how to learn. Now, learn.