Adobe Interview Question
Computer ScientistsCountry: United States
/* ? replaces one character
* replaces zero or more characters
*/
int wildmatch(char* s, char *p){
if(s[0]==0 && p[0]==0) return 1;
else if(s[0]==0){
while(p[0]=='*')p++;
if(p[0]!=0)return -1;
else return 1;
}
else if(p[0]==0)return 0;
if(p[0]==s[0] || p[0]=='?')
return wildmatch(s+1,p+1);
else if(p[0]=='*'){
if(p[1]==0)return 1;
int ret=0;
int i=0;
while(ret==0){
ret=wildmatch(s+i,p+1);
i++;
}
if(ret==-1) return -1;
else return 1;
}
else return 0;
}
/* ? replaces one character
* replaces zero or more characters
*/
int wildmatch(char* s, char *p){
if(s[0]==0 && p[0]==0) return 1;
else if(s[0]==0){
while(p[0]=='*')p++;
if(p[0]!=0)return -1;
else return 1;
}
else if(p[0]==0)return 0;
if(p[0]==s[0] || p[0]=='?')
return wildmatch(s+1,p+1);
else if(p[0]=='*'){
if(p[1]==0)return 1;
int ret=0;
int i=0;
while(ret==0){
ret=wildmatch(s+i,p+1);
i++;
}
if(ret==-1) return -1;
else return 1;
}
else return 0;
}
wildmatch (agcbc, a*b?)=1
bool wildmatch (char *string, char *pattern):
if (*pattern == ‘\n’ && *string == ‘\n') {
return true;
}
if (*string == ‘\n') {
return false;
}
if (*pattern == *string || *pattern = ‘?') {
wildmatch (string++, pattern++);
}
while (*pattern == ‘*’) {
pattern++;
}
while (*string != *pattern && *string != ‘\n') {
string++;
}
wildmatch (string, pattern);
}
Given:
? - any char
* - any string
wildmatch (agcbc, a*ba) is supposed to return 0, isn't it?
bool wildmatch(string s,string sPattern)
{
if(s.length() == 1 && sPattern.length() == 1 && s[0] == sPattern[0])
return true;
if(s.length() == 1 || sPattern.length() == 1)
return false;
if((s[0] == sPattern[0]) || sPattern[0] == '?')
{
return wildmatch(s.substr(1),sPattern.substr(1));
}
else if(sPattern[0] == '*' && s[0] != sPattern[1])
{
return wildmatch(s.substr(1),sPattern);
}else if(sPattern[0] == '*' && s[0] == sPattern[1])
{
return wildmatch(s.substr(1),sPattern.substr(2));
}
return false;
}
static boolean wildMatchRecursive(String pattern, String s){
if((pattern.length()==1 && s.length()==1) && (pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?')){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='*'){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='?'){
return false;
}
if(pattern.length()==1 && s.length()==1){
return false;
}
if(pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?'){
return wildMatchRecursive(pattern.substring(1), s.substring(1));
}else if(pattern.charAt(0)=='*'){
System.out.println("$$ " + s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
//return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.length()-(pattern.substring(pattern.indexOf('*')+1)).length()));
return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
}
return false;
}
static boolean wildMatchRecursive(String pattern, String s){
if((pattern.length()==1 && s.length()==1) && (pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?')){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='*'){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='?'){
return false;
}
if(pattern.length()==1 && s.length()==1){
return false;
}
if(pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?'){
return wildMatchRecursive(pattern.substring(1), s.substring(1));
}else if(pattern.charAt(0)=='*'){
System.out.println("$$ " + s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
//return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.length()-(pattern.substring(pattern.indexOf('*')+1)).length()));
return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
}
return false;
}
static boolean wildMatchRecursive(String pattern, String s){
if((pattern.length()==1 && s.length()==1) && (pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?')){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='*'){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='?'){
return false;
}
if(pattern.length()==1 && s.length()==1){
return false;
}
if(pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?'){
return wildMatchRecursive(pattern.substring(1), s.substring(1));
}else if(pattern.charAt(0)=='*'){
System.out.println("$$ " + s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
//return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.length()-(pattern.substring(pattern.indexOf('*')+1)).length()));
return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
}
return false;
}
static boolean wildMatchRecursive(String pattern, String s){
if((pattern.length()==1 && s.length()==1) && (pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?')){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='*'){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='?'){
return false;
}
if(pattern.length()==1 && s.length()==1){
return false;
}
if(pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?'){
return wildMatchRecursive(pattern.substring(1), s.substring(1));
}else if(pattern.charAt(0)=='*'){
System.out.println("$$ " + s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
//return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.length()-(pattern.substring(pattern.indexOf('*')+1)).length()));
return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
}
return false;
}
static boolean wildMatchRecursive(String pattern, String s){
if((pattern.length()==1 && s.length()==1) && (pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?')){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='*'){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='?'){
return false;
}
if(pattern.length()==1 && s.length()==1){
return false;
}
if(pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?'){
return wildMatchRecursive(pattern.substring(1), s.substring(1));
}else if(pattern.charAt(0)=='*'){
System.out.println("$$ " + s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
//return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.length()-(pattern.substring(pattern.indexOf('*')+1)).length()));
return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
}
return false;
}
static boolean wildMatchRecursive(String pattern, String s){
if((pattern.length()==1 && s.length()==1) && (pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?')){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='*'){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='?'){
return false;
}
if(pattern.length()==1 && s.length()==1){
return false;
}
if(pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?'){
return wildMatchRecursive(pattern.substring(1), s.substring(1));
}else if(pattern.charAt(0)=='*'){
System.out.println("$$ " + s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
//return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.length()-(pattern.substring(pattern.indexOf('*')+1)).length()));
return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
}
return false;
}
static boolean wildMatchRecursive(String pattern, String s){
if((pattern.length()==1 && s.length()==1) && (pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?')){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='*'){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='?'){
return false;
}
if(pattern.length()==1 && s.length()==1){
return false;
}
if(pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?'){
return wildMatchRecursive(pattern.substring(1), s.substring(1));
}else if(pattern.charAt(0)=='*'){
System.out.println("$$ " + s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
//return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.length()-(pattern.substring(pattern.indexOf('*')+1)).length()));
return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
}
return false;
}
static boolean wildMatchRecursive(String pattern, String s){
if((pattern.length()==1 && s.length()==1) && (pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?')){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='*'){
return true;
}
if(pattern.length()==1 && pattern.charAt(0)=='?'){
return false;
}
if(pattern.length()==1 && s.length()==1){
return false;
}
if(pattern.charAt(0)==s.charAt(0) || pattern.charAt(0)=='?'){
return wildMatchRecursive(pattern.substring(1), s.substring(1));
}else if(pattern.charAt(0)=='*'){
System.out.println("$$ " + s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
//return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.length()-(pattern.substring(pattern.indexOf('*')+1)).length()));
return wildMatchRecursive(pattern.substring(pattern.indexOf('*')+1),s.substring(s.indexOf((pattern.charAt(pattern.indexOf('*')+1)))));
}
return false;
}
- nikolay.dimitrov April 17, 2015