Given an input string (v) and a pattern, implement a wildcard matching function with support for literal characters a through z and the wildcard character * (which matches zero or more of any character).
static boolean isMatch(String v, String pattern)
cat ct ---> true
cat t ---> true
dog ct ---> false
cat tac* --->false
what are allowed wild cards?
/
/
s pointer to iterate on string
p pointer to iterate on pattern
*/
class Solution {
public static void main(String[] args) {
boolean res = isMatch("cat","c*t");
System.out.println("cat c*t "+res);
res = isMatch("cat","*t");
System.out.println("cat *t " +res);
res = isMatch("dog","c*t");
System.out.println("dog c*t "+res);
res = isMatch("cat","*t*a*c*");
System.out.println("cat *t*a*c* "+res);
res = isMatch("catcatcat","cat*cat*cat***");
System.out.println("catcatcat cat*cat*cat*** "+res);
res = isMatch("fdajhfjdsacatcatcatlsaflk","****cat*cat*cat***");
System.out.println("fdajhfjdsacatcatcatlsaflk ****cat*cat*cat*** "+res);
res = isMatch("catdog","cat*cat*");
System.out.println("catdog cat*cat* "+res);
res = isMatch("", "*");
System.out.println(" *"+res);
res = isMatch("cat", "cat*cat");
System.out.println("cat cat*cat "+res);
res = isMatch("catat", "ca*t");
System.out.println("catat ca*t "+res);
/*ArrayList<String> strings = new ArrayList<String>();
strings.add("Hello, World!");
strings.add("Welcome to CoderPad.");
strings.add("This pad is running Java " + Runtime.version().feature());
for (String string : strings) {
System.out.println(string);
}*/
}//O(Max(N,M))
private static boolean isMatch(String v, String pattern){
int s=0, p=0, newS = -1, newP = -1;
while(s<v.length()){
if(p<pattern.length() && v.charAt(s) == pattern.charAt(p)){
s++;
p++;
continue;
}
if(p<pattern.length() && pattern.charAt(p) == '*') {
newS = s; newP=p++;
continue;
}
if(newP != -1){ // we have *
p = newP++;
s = ++newS;
continue;
}
return false;
}
// System.out.println("s = "+s+", v.length() = "+v.length()+", p = "+p+", pattern.length() "+pattern.length());
while(p<pattern.length() && pattern.charAt(p) == '*') p++;
return s== v.length() && p==pattern.length();
}
}Comments (15)