Created
November 19, 2018 02:48
-
-
Save Abhishek-Chaudhary-InfoCepts/2b34e44cf13fc93a9e38ec4741c7d1c1 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package com.interview.dynamic; | |
public class WildCardMatching { | |
public boolean isMatch(String s, String p) { | |
char[] str = s.toCharArray(); | |
char[] pattern = p.toCharArray(); | |
//replace multiple * with one * | |
//e.g a**b***c --> a*b*c | |
int writeIndex = 0; | |
boolean isFirst = true; | |
for ( int i = 0 ; i < pattern.length; i++) { | |
if (pattern[i] == '*') { | |
if (isFirst) { | |
pattern[writeIndex++] = pattern[i]; | |
isFirst = false; | |
} | |
} else { | |
pattern[writeIndex++] = pattern[i]; | |
isFirst = true; | |
} | |
} | |
boolean T[][] = new boolean[str.length + 1][writeIndex + 1]; | |
if (writeIndex > 0 && pattern[0] == '*') { | |
T[0][1] = true; | |
} | |
T[0][0] = true; | |
for (int i = 1; i < T.length; i++) { | |
for (int j = 1; j < T[0].length; j++) { | |
if (pattern[j-1] == '?' || str[i-1] == pattern[j-1]) { | |
T[i][j] = T[i-1][j-1]; | |
} else if (pattern[j-1] == '*'){ | |
T[i][j] = T[i-1][j] || T[i][j-1]; | |
} | |
} | |
} | |
return T[str.length][writeIndex]; | |
} | |
/** | |
* Recursive and slow version of wild card matching. | |
*/ | |
public boolean isMatchRecursive(String s, String p) { | |
return isMatchRecursiveUtil(s.toCharArray(), p.toCharArray(), 0, 0); | |
} | |
private boolean isMatchRecursiveUtil(char[] text, char[] pattern, int pos1, int pos2) { | |
if (pos2 == pattern.length) { | |
return text.length == pos1; | |
} | |
if (pattern[pos2] != '*') { | |
if (pos1 < text.length && (text[pos1] == pattern[pos2]) || pattern[pos2] == '?') { | |
return isMatchRecursiveUtil(text, pattern, pos1 + 1, pos2 + 1); | |
} else { | |
return false; | |
} | |
} else { | |
//if we have a***b then skip to the last * | |
while (pos2 < pattern.length - 1 && pattern[pos2 + 1] == '*') { | |
pos2++; | |
} | |
pos1--; | |
while (pos1 < text.length) { | |
if (isMatchRecursiveUtil(text, pattern, pos1 + 1, pos2 + 1)) { | |
return true; | |
} | |
pos1++; | |
} | |
return false; | |
} | |
} | |
public static void main(String args[]) { | |
WildCardMatching wcm = new WildCardMatching(); | |
System.out.println(wcm.isMatch("xbylmz", "x?y*z")); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment