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 edgecase 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(j1);
if(currTextChar != prevPatternChar) { // this means the '*'
// denotes no character
i = i  1; // restore i to current position
j = j + 1; // after it's reincrement 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*"));
}
}

Killedsteel
February 13, 2014 Check out Wikipedia for the medianofmedians 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;

Killedsteel
February 13, 2014 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 nonetheless!
 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 (n1). So I guess it is a compromise.
 Killedsteel February 09, 2014Open Chat in New Window
If not the function, atleast it's prototype.
 Killedsteel February 13, 2014