/* package whatever; // don't place package name! */
import java.util.*;
import java.lang.*;
import java.io.*;
/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
// base case 1: we came to end in both string and pattern -> matched
if (str.length() == 0 && pattern.length() == 0) {
return true;
}
// base case 2: we came to end in string, but pattern contains more symbols (and it is not '*')
if (str.length() == 0 && !pattern.equals("*")) {
return false;
}
// checking the next symbol matching
if (charsMatch(pattern, '?') || charsMatch(pattern, str)) {
return matches(pattern.substring(1), str.substring(1));
}
// checking wildcard - there are two scenarios: either we skip the wildcard, or we skip the next symbol
if (charsMatch(pattern, '*')) {
return matches(pattern.substring(1), str) || matches(pattern, str.substring(1));
}
return false;
}
private static boolean charsMatch
(String s,
char ch
) { return s.length() > 0 && s.charAt(0) == ch;
}
return s.length() > 0 && p.length() > 0 && s.charAt(0) == p.charAt(0);
}
public static void main
(String[] args
) { eq("g*ks", "geeks"); // Yes
eq("ge?ks*", "geeksforgeeks"); // Yes
neq("g*k", "gee"); // No because 'k' is not in second
neq("*pqrs", "pqrst"); // No because 't' is not in first
eq("abc*bcd", "abcdhghgbcd"); // Yes
neq("abc*c?d", "abcd"); // No because second must have 2 instances of 'c'
eq("*c*d", "abcd"); // Yes
eq("*?c*d", "abcd"); // Yes
}
assert matches(s, s2);
}
assert !matches(s, s2);
}
}
LyogcGFja2FnZSB3aGF0ZXZlcjsgLy8gZG9uJ3QgcGxhY2UgcGFja2FnZSBuYW1lISAqLwoKaW1wb3J0IGphdmEudXRpbC4qOwppbXBvcnQgamF2YS5sYW5nLio7CmltcG9ydCBqYXZhLmlvLio7CgovKiBOYW1lIG9mIHRoZSBjbGFzcyBoYXMgdG8gYmUgIk1haW4iIG9ubHkgaWYgdGhlIGNsYXNzIGlzIHB1YmxpYy4gKi8KY2xhc3MgSWRlb25lCnsKICAgIHB1YmxpYyBzdGF0aWMgYm9vbGVhbiBtYXRjaGVzKFN0cmluZyBwYXR0ZXJuLCBTdHJpbmcgc3RyKSB7CiAgICAgICAgLy8gYmFzZSBjYXNlIDE6IHdlIGNhbWUgdG8gZW5kIGluIGJvdGggc3RyaW5nIGFuZCBwYXR0ZXJuIC0+IG1hdGNoZWQKICAgICAgICBpZiAoc3RyLmxlbmd0aCgpID09IDAgJiYgcGF0dGVybi5sZW5ndGgoKSA9PSAwKSB7CiAgICAgICAgICAgIHJldHVybiB0cnVlOwogICAgICAgIH0KICAgICAgICAvLyBiYXNlIGNhc2UgMjogd2UgY2FtZSB0byBlbmQgaW4gc3RyaW5nLCBidXQgcGF0dGVybiBjb250YWlucyBtb3JlIHN5bWJvbHMgKGFuZCBpdCBpcyBub3QgJyonKQogICAgICAgIGlmIChzdHIubGVuZ3RoKCkgPT0gMCAmJiAhcGF0dGVybi5lcXVhbHMoIioiKSkgewogICAgICAgICAgICByZXR1cm4gZmFsc2U7CiAgICAgICAgfQogICAgICAgIC8vIGNoZWNraW5nIHRoZSBuZXh0IHN5bWJvbCBtYXRjaGluZwogICAgICAgIGlmIChjaGFyc01hdGNoKHBhdHRlcm4sICc/JykgfHwgY2hhcnNNYXRjaChwYXR0ZXJuLCBzdHIpKSB7CiAgICAgICAgICAgIHJldHVybiBtYXRjaGVzKHBhdHRlcm4uc3Vic3RyaW5nKDEpLCBzdHIuc3Vic3RyaW5nKDEpKTsKICAgICAgICB9CiAgICAgICAgLy8gY2hlY2tpbmcgd2lsZGNhcmQgLSB0aGVyZSBhcmUgdHdvIHNjZW5hcmlvczogZWl0aGVyIHdlIHNraXAgdGhlIHdpbGRjYXJkLCBvciB3ZSBza2lwIHRoZSBuZXh0IHN5bWJvbAogICAgICAgIGlmIChjaGFyc01hdGNoKHBhdHRlcm4sICcqJykpIHsKICAgICAgICAgICAgcmV0dXJuIG1hdGNoZXMocGF0dGVybi5zdWJzdHJpbmcoMSksIHN0cikgfHwgbWF0Y2hlcyhwYXR0ZXJuLCBzdHIuc3Vic3RyaW5nKDEpKTsKICAgICAgICB9CiAgICAgICAgcmV0dXJuIGZhbHNlOwogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIGJvb2xlYW4gY2hhcnNNYXRjaChTdHJpbmcgcywgY2hhciBjaCkgewogICAgICAgIHJldHVybiBzLmxlbmd0aCgpID4gMCAmJiBzLmNoYXJBdCgwKSA9PSBjaDsKICAgIH0KICAgIHByaXZhdGUgc3RhdGljIGJvb2xlYW4gY2hhcnNNYXRjaChTdHJpbmcgcywgU3RyaW5nIHApIHsKICAgICAgICByZXR1cm4gcy5sZW5ndGgoKSA+IDAgJiYgcC5sZW5ndGgoKSA+IDAgJiYgcy5jaGFyQXQoMCkgPT0gcC5jaGFyQXQoMCk7CiAgICB9CgogICAgcHVibGljIHN0YXRpYyB2b2lkIG1haW4oU3RyaW5nW10gYXJncykgewogICAgICAgIGVxKCJnKmtzIiwgImdlZWtzIik7IC8vIFllcwogICAgICAgIGVxKCJnZT9rcyoiLCAiZ2Vla3Nmb3JnZWVrcyIpOyAvLyBZZXMKICAgICAgICBuZXEoImcqayIsICJnZWUiKTsgIC8vIE5vIGJlY2F1c2UgJ2snIGlzIG5vdCBpbiBzZWNvbmQKICAgICAgICBuZXEoIipwcXJzIiwgInBxcnN0Iik7IC8vIE5vIGJlY2F1c2UgJ3QnIGlzIG5vdCBpbiBmaXJzdAogICAgICAgIGVxKCJhYmMqYmNkIiwgImFiY2RoZ2hnYmNkIik7IC8vIFllcwogICAgICAgIG5lcSgiYWJjKmM/ZCIsICJhYmNkIik7IC8vIE5vIGJlY2F1c2Ugc2Vjb25kIG11c3QgaGF2ZSAyIGluc3RhbmNlcyBvZiAnYycKICAgICAgICBlcSgiKmMqZCIsICJhYmNkIik7IC8vIFllcwogICAgICAgIGVxKCIqP2MqZCIsICJhYmNkIik7IC8vIFllcwogICAgfQoKICAgIHByaXZhdGUgc3RhdGljIHZvaWQgZXEoU3RyaW5nIHMsIFN0cmluZyBzMikgewogICAgICAgIGFzc2VydCBtYXRjaGVzKHMsIHMyKTsKICAgIH0KICAgIHByaXZhdGUgc3RhdGljIHZvaWQgbmVxKFN0cmluZyBzLCBTdHJpbmcgczIpIHsKICAgICAgICBhc3NlcnQgIW1hdGNoZXMocywgczIpOwogICAgfQp9