CareerCup

public static boolean match(char text[], char pattern[]) {
		if (text == null || text.length == 0) return false;
		if (pattern == null || pattern.length == 0) return false;
		
		for (int i=0, j=0; i<text.length; i++) {
			if (pattern[j] == '.') {
				j++;
			}
			else if (j > 0 && pattern[j] == '*') {
				if (text[i] != pattern[j-1]) {
					if (text[i] == pattern[j+1]) {
						j++;
					}
					else {
						return false;
					}
				}
			}
			else {
				if (text[i] != pattern[j]) {
					return false;
				}
				else {
					j++;
				}
			}
		}
		
		
		return true;
	}

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*"));
    }
}

Here is a basic recursive solution. Few check like the first string should only have alphabets and digits can also be added

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class StringMatch {
	public static void main(String[] args) throws IOException {
		BufferedReader obj = new BufferedReader(new InputStreamReader(System.in));
		System.out.println("Enter the main String");
		String input1 = obj.readLine();
		System.out.println("Enter the second String ");
		String input2 = obj.readLine();
		boolean matchSuccessful=match(input1,input2,input1.length(),input2.length());
	    System.out.println(matchSuccessful);
	}

	private static boolean match(String input1, String input2, int i, int j) {
		if(i==0 && j==0)
		return true;
		else{
			if(input1.charAt(0)==input2.charAt(0)||input2.charAt(0)=='.')
				return match(input1.substring(1),input2.substring(1),i-1,j-1);
			else if(input2.charAt(0)=='*'){
				return match(input1.substring(1),input2.substring(1),i-1,j-1)||match(input1.substring(1),input2,i-1,j);
			}
		}
		return false;
	}

}

public static boolean compaire(String st, String pattern) {
        boolean result = false;
        if (st.length() == pattern.length()) {
            char a1[] = st.toCharArray();
            char a2[] = pattern.toCharArray();
            for (int i = 0; i < a1.length; i++) {
                System.out.println(" First "+a1[i]+" Second "+a2[i] );
                if (a1[i] == a2[i]) {
                    result = true;
                } else {
                    if (a2[i] == '.') {
                        if ((a1[i] >= 'a' && a1[i] <= 'z') || (a1[i] >= 'A' && a1[i] <= 'Z') || (a1[i] >= '0' && a1[i] <= '9')) {
                            result = true;
                        } else {
                            return false;
                        }
                    } else if (a2[i] == '*') {
                        
                        if (i > 0 && (a2[(i-1)] == a1[i])) {
                            result = true;
                        } else {
                            return false;
                        }
                    } else {
                        return false;
                    }
                }
            }
        } else {
            return false;
        }
        return result;
    }

public class MatchExp {
    static boolean match(String input, String match){
        return matchExp(input.toLowerCase(),match.toLowerCase(),0,0);
    }

    static boolean  matchExp(String input, String match, int i, int j){


        if(i==input.length() && j==match.length()) return true;
        if(i==input.length()) return false;
        if(j==match.length()) return false;

        if(match.charAt(j)=='*'){
            boolean matchVal = false;
            for(int k  = i;k<input.length();k++){
                matchVal |= matchExp(input,match,k,j+1);
            }
            return matchVal;
        }

        return (match.charAt(j) == input.charAt(i) || match.charAt(j) == '.') && matchExp(input, match, i + 1, j + 1);

    }

    public static void main(String arvg[]){
       Boolean ans =  match("facebook123","F.cebo*k12*3");
       System.out.print(ans);
    }
}

public static boolean doesPatternMatch(String text, String patt)
{
//dp[i][j] = true if first "i" characters of pattern matches with first "j" characters of text
boolean[][] dp = new boolean[patt.length()][text.length()];


//base case
if(patt.charAt(0)=='.' || patt.charAt(0) == text.charAt(0))
{
dp[0][0]=true;
}else{
dp[0][0]=false;
}

for(int k=1;k<text.length();k++)
{
if(patt.charAt(0) == '*')
dp[0][k]=true;
else
dp[0][k]=false;
}

for(int k=1;k<patt.length();k++)
{
if(patt.charAt(k) == '*')
{
dp[k][0] = dp[k-1][0];
}else
{
dp[k][0]=false;
}
}


for(int i=1;i<patt.length();i++)
{
for(int j=1;j<text.length();j++)
{
if(patt.charAt(i) == '*')
{
dp[i][j] = dp[i-1][j-1] || dp[i-1][j];
}else if(patt.charAt(i) == '.')
{
dp[i][j] = dp[i-1][j-1];
}else if(patt.charAt(i) == text.charAt(j))
{
dp[i][j] = true;
}else{
dp[i][j] = false;
}
}
}

return dp[patt.length()-1][text.length()-1];
}

Here is the C code:

bool is_match(char * str1,char * str2)
{
    //str2 has wildcard characters
    //1. '.' means match single character
    //2. '*' means previous character repeat 0 or # of times
    //base case
    if(*str1 == '\0')
    {
        if(*str2 != '\0' && *str2 != '*')
        return false;   //doesn't match
        while(*str2 == '*')
        str2++;
        if(*str2 == '\0')
        return true;
        else
        return false;
    }
    if(*str1 && !(*str2))
    return false;
    
    if(*str2 == '.')    //1 character match
    return is_match(str1+1,str2+1);
    else if(*str2 == '*')
return ((is_match(str1,str2+1)) || (*str1 == *(str1+1)?is_match(str1+1,str2):is_match(str1+1,str2+1)));
   else 
   {
       if(*str1 == *str2)
       return is_match(str1+1,str2+1);
       else
       return false;
   }
}

def match2(s1, s2, prev=None):
    if not len(s1):
        return True
    elif s1[0] == s2[0]:
        return match2(s1[1:], s2[1:], s2[0])
    elif s2[0] == "." and (str.isdigit(s1[0]) or str.isalpha(s1[0])):
        return match2(s1[1:], s2[1:], s2[0])
    elif s2[0] == "*" and s1[0] == prev:
        return match2(s1[1:], s2, prev)
    elif s2[0] == "*" and s1[0] != prev:
        return match2(s1, s2[1:], s2[0])
    return False

I have question I saw comment that the code should return true for StringMatchWithWildCards.matchStrings("Facebook", "Facebo*ok") but isn't pattern equivalent to Faceboook and it should rather fail?

boolean isAMatch(int s_idx, int p_idx) {

if(s_idx == str.length() && p_idx == pat.length()) {
return true;
}

if(s_idx == str.length() || p_idx == pat.length()) {
return false;
}

if(str.charAt(s_idx) == pat.charAt(p_idx)) {
return isAMatch(s_idx+1, p_idx+1);
}

else if(pat.charAt(p_idx) == '.') {
return isAMatch(s_idx+1, p_idx+1);
}
else if(pat.charAt(p_idx) == '*') {

boolean case_A = false;
boolean case_C = false;
if(s_idx+1 < str.length() && str.charAt(s_idx+1) == str.charAt(s_idx)) {
case_A = isAMatch(s_idx+1, p_idx);
}
//0 characters
boolean case_B = isAMatch(s_idx, p_idx+1);
//both match
if(p_idx > 0 && str.charAt(s_idx) == pat.charAt(p_idx-1)) {
case_C = isAMatch(s_idx+1, p_idx+1);
}
return ( case_A || case_B ||case_C);
}
return false;
}

bool ismatch(const char* s, const char* p)
{
	if(!s || !p) return false;
	if(*p == '\0') return *s == '\0';
	if(*(p+1) == '*'){
		if(*s == *p || (*p == '.' && *s != '\0')) return ismatch(s+1, p) || ismatch(s, p+2);
		return ismatch(s, p+2);
	}
	else{
		if(*s == *p || (*p == '.' && *s != '\0')) return ismatch(s+1, p+1);
		return false;
	}
}

Ok , it was telephonic . I will explain logic
Assuming there can be more than one occurrence of *
Taking example /temp/*my*jpeg

Calculate firstst occurrence of *
Calculate lastst occurrence of *
So know you know the prefix ans sufix string which need to be matched
Figure out how many middleStrings can be there .( You know the first occurance of * , so add +1 to that position and find next occurance of * . this way do till you reach lastst *)
Now simply use substring method for all the string which you have found ( i.e. prefix string,middle strings and sufix string)

I do not think this is a perfect algorithm but this is what I could do in the whiteboard.

public static bool IsMatch(string S, string P)
{
	int ppos = 0;
	int spos = 0;
	while(ppos < P.Length && spos < S.Length)
	{
		char p = P[ppos];
		char s = S[spos];

		if(p == s || p == '.')
		{
			ppos++;
			spos++;
		}
		else if(p == '*')
		{
			if(ppos < P.Length - 1 && s == P[ppos + 1])
			{
				spos++;
				ppos += 2;
			}
			else if(ppos > 0 && (s == P[pos - 1] || P[ppos-1] == '.'))
			{
				spos++;
			}
			else
				return false;
		}
		else 
			return false;
		
	}

	return (ppos == P.Length && spos == P.Length);
}

function func($pattern,$string) {
	if (strpos($pattern,"**") !== false || strpos($pattern,"*") === 0) 
		return false;

	$pi = 0;
	$si = 0;
	do {
		$p_chr = $pattern[$pi];
		$s_chr = $string[$si];

		if ($p_chr == $s_chr || $p_chr == '.') {
			$pi++;
			$si++;
		} elseif ($p_chr == '*') {	
			$masterChar = $string[$si-1];
			while ($string[$si] == $masterChar) $si++;
			$pi++;
		} elseif ($pattern[$pi+1] == '*') {
			$pi+=2;
		} else {
			return false;
		}

	}while($p_chr != null || $s_char != null);
	
	return true;
}

var_dump(func("aaa","aaa") == true);
var_dump(func("aaak","aaa") == false);
var_dump(func("aaa","aaak") == false);
var_dump(func("a.a","ana") == true);
var_dump(func(".aa.","jaan") == true);
var_dump(func("aaa","bbb") == false);
var_dump(func(".aa","bbb") == false);
var_dump(func("ab*g","ag") == true);
var_dump(func("ab*g","abg") == true);
var_dump(func("ab*g","abbg") == true);
var_dump(func("ab*","abbb") == true);
var_dump(func("b*","") == true);
var_dump(func(".*.","jjjjjm") == true);
var_dump(func("*aaa","a") == false);
var_dump(func("aa***a","a") == false);
var_dump(func(".","j") == true);