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.
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 ?
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
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
}
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
