Killedsteel
BAN USERBecause I love algorithms and math! I believe that each algorithm is backed by strong fundamental mathematics, and it is that mathematics that I like to uncover.
Btw, ignore the following comment in the code. It was just something I was thinking of.
// pattern can never be longer
// than the original text
Explanation: The code basically checks each of the edge cases iteratively. The '*' character could be at the end, or at the second position. Consecutively, pattern.length may be greater than text.length, or vice versa.
Note: I forgot to implement the edge-case where the '*' character is the first character in the pattern string. In this case, it probably makes sense to throw an IllegalArgumentException exception. Maybe I can leave this as an exercise for someone to implement :)
Here is my working code in Java:
public class StringMatchWithWildCards {
public static boolean matchStrings(String text, String pattern) {
int lengthText = text.length();
int lengthPattern = pattern.length();
int i = 0;
int j = 0;
while(i < lengthText) {
if(j == lengthPattern) // pattern can never be longer
return false; // than the original text
if(text.charAt(i) == pattern.charAt(j) || pattern.charAt(j) == '.') {
j = j + 1;
}
else if (pattern.charAt(j) == '*') {
// here, we need to count instances
// in text, that correspond to this
// character.
char currTextChar = text.charAt(i);
char prevPatternChar = pattern.charAt(j-1);
if(currTextChar != prevPatternChar) { // this means the '*'
// denotes no character
i = i - 1; // restore i to current position
j = j + 1; // after it's re-increment by 1
}
else {
// fast forward i to point to character
// where (currTextChar != prevPatternChar)
while(i < lengthText && currTextChar == prevPatternChar) {
currTextChar = text.charAt(i);
i = i + 1;
}
if(i == lengthText) {// text reached end first
return (j == lengthPattern - 1);
}
else {
i = i - 1; // same as above. ready for
j = j + 1; // next piece of string matching
}
}
}
else return false;
i = i + 1;
}
return (i == lengthText && j == lengthPattern);
}
}
Also, here is the test class:
public class StringMatchWithWildCardsTest {
@Test
public void testMatchStrings() {
Assert.assertFalse(StringMatchWithWildCards.matchStrings("Facebook", "F*cebo.k"));
Assert.assertTrue(StringMatchWithWildCards.matchStrings("Facebook", "F.cebo.k"));
Assert.assertTrue(StringMatchWithWildCards.matchStrings("Facebooo", "Facebo*"));
Assert.assertFalse(StringMatchWithWildCards.matchStrings("Facebooker", "F.cebo*"));
}
}
Check out Wikipedia for the median-of-medians algorithm. It provides an answer to your question in O(n) time.
- Killedsteel February 13, 2014Wouldn't this fail for the following test case?
Text: Facebook
Pattern: Fac*book
What the ' * ' represents is _not_ a simple replacement for multiple characters, but a replacement for repetition of zero or more instances of the _previous_ character.
Lol, the problem is here:
if(root=NULL)
return 0;
This is an assignment operation. What you really want, is this:
if(root == NULL)
return 0;
Nice solution. This is indeed O(n log(n)). However, I think that if you use a TreeSet instead of a PriorityQueue, I think you can bring it down to O(n log(m)). If m << n, this can make a huge difference! :)
- Killedsteel February 10, 2014@techpanja : Good but deceptive solution. On the face of it, it looks like it is O(n) in time, where n = length of input string. However, it is really O(n*k) in time, where k = number of characters required. This is because the ".substring(int beginIdx, int endIdx)" function doesn't come with O(1) but with O(endIdx - beginIdx) which is O(k) here. Interesting solution none-the-less!
- Killedsteel February 09, 2014@PiysuhRai: May be that is true. But KMP is space efficient too. With Tries, I'm assuming you'll need O(n^2) space since you'll have to store substrings starting at each position starting from 0 to (n-1). So I guess it is a compromise.
- Killedsteel February 09, 2014
If not the function, atleast it's prototype.
- Killedsteel February 13, 2014