# See if two Strings are the same using recursivity (recursion)

For a given character string, called, write a recursive function
Boolean check(String s, String pattern)
Which determines whether the given pattern matches the string. The pattern consists of letters and the special character ‘?’ which means “any letter”. The pattern matches the character string s when all the characters in the pattern match all the characters in s.

For example :

check(“test”, “test”) returns true
check(“test”, “tes”) returns false
check(“test”, “t?st our”) return true

``````boolean check(String s, String pattern){

int M = s.length();
int N = pattern.length();
//int i=0;

//print(s);

if(M > N || M < N){
print(false);
return false;

}
if(M==0 && N==0){
print(false);
return false;

}

if (s.charAt(0) == pattern.charAt(0)) {

return check(s.substring(1), pattern.substring(1));
} else {
print("false");
return false;

}

}

I am here right now I dont know if I am on the write path in my code. Any tips ?

``````

Hi @oussama10 ,

Where is the question in your post? Is it a homework assignment that you have to do? Hello, thank you for your reply. No not at all I have an exam tomorrow and we could get this type of question. I am trying to understand it before my exam I understood the idea and everything but I am having a hard time write it in my code

Ah sorry I didn’t see the last sentence, you need to delimit your code with backticks properly ```code``` → `code`

Note that this is a Processing forum, not a general computer science related forum Please post a complete runable program not only the function.

The “right path”

I have not tried your code but you seem to be on the right track but you need to test for wild cards - try

`if (s.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '?') {`

Apart from that your code is a little ‘untidy’ try using Ctrl + T in Processing IDE to correct that.

1 Like

Remark 1

if (M > N || M < N) {

is

if (M != N) {

but the entire condition is an mistake anyway because in the 3rd example, both are not of the same length and it still must return true ( `check(“test”, “t?st our”) return true` ) and not false.

Remark 2

you need a statement that returns true when the last letter has been reached.

Remark 3

In my opinion the assignment itself is a bit weird. When you think about it, normally you have a text (The Bible) where you search a word (Jesus).

The text doesn’t contain placeholders only the search word does (so the search word contains a ‘?’ not the text; therefore the search word is called pattern not the text).

In the assignment this is mixed up. We search a word s within the text named “pattern” (see example 3) but the terminology is a bit messed up in my humble opinion.

OR did you write the 3 examples? Maybe they are incorrect?

Quote:

Technically this is not true for example 3. The wording should be:

• The pattern (search word) matches the character string s [The Bible Text] when all the characters in the pattern occur in s (without other letters in between and in the correct same order (apart from placeholder “?”)).

I don’t know.

My Code

My code works (or seems to work) for your 3 examples but is far from perfect

``````
// recursion test

void setup() {

size (110, 110);

//should return true
if (check("test", "test"))
println("Yes");
else  println("No");

//returns false
if (check("test", "tes"))
println("Yes");
else  println("No");

// return true
if (check("test", "t?st our"))
println("Yes");
else  println("No");
}

boolean check(String s, String pattern) {

int M = s.length();
int N = pattern.length();

//print(M);
//println(s);

// When the LAST letter of s has been reached and it's okay, we finally can return true (FINAL condition ends the recursion with true)
if (M==1 && N>=1 &&
(s.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '?')  ) {
return true;
}

// not sure about this (when we look at example 1, it should return true (not false)! But this won't work on example 3 because M < N)
if (M==0 && N==0) {
// print(false);
// return false;
// return true;
}

if ( (M>=1 && N>=1) &&
(s.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '?')) {
// valid, keep on
return check(s.substring(1), pattern.substring(1));
} else {
// not valid, abort (end recursion with negative outcome)
//println("false");
return false;
}
}
//

``````

I am going to take you at your word that it is not homework and that it is for learning purposes.

Here is my solution with comments

``````boolean check(String s, String pattern) {
int m = s.length();
int n = pattern.length();
// If either string has characters left compare the first character
// in each string and if the same recurse
if (m > 0 && n > 0
&& (s.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '?')) {
return check(s.substring(1), pattern.substring(1));
}
// Terminating condition reached - if we have consumed all possible
// characters the strings are the same (incl same length)
return (m == 0 && n == 0);
}

void setup() {
println(check("quark", "uark"));     // false
println(check("quark", "quark"));    // true
println(check("quark", "Quark"));    // false
println(check("quark", "?uar?"));    // true
println(check("quark", "quack"));    // false
println(check("quark", "?????"));    // true
}
``````
1 Like

We can easily modify it to make the test case insensitive like this

``````boolean check(String s, String pattern) {
int m = s.length();
int n = pattern.length();
// If either string has characters left compare the first character
// in each string and if the same recurse
if (m > 0 && n > 0  &&
(s.charAt(0) == pattern.charAt(0) || pattern.charAt(0) == '?'
|| (s.charAt(0) ^ pattern.charAt(0)) == 32)) {
return check(s.substring(1), pattern.substring(1));
}
// Terminating condition reached - if we have consumed all possible
// characters the strings are the same (incl same length)
return (m == 0 && n == 0);
}
``````

The third test is now true. I leave you to find out how it works 1 Like