CareerCup

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Ideone
{
	public static void main (String[] args) throws java.lang.Exception
	{
		System.out.println("Match " + stringMatching("abcddd", "abcd*"));
		System.out.println("Match " + stringMatching("ccca", "c*a"));
		System.out.println("Match " + stringMatching("ab", ".*"));
		System.out.println("Match " + stringMatching("abcdefg", "a*c..f*"));
	}
	
	public static boolean stringMatching(String string, String pattern){
		System.out.println("String " + string + " pattern " + pattern);
		if(pattern == null || pattern.length() == 0 || (pattern.equals("*") && string!=null) || (pattern.equals(".") && string.length() == 1) || pattern.equals(string)){
			return true;
		}
		char firstOfPattern = pattern.charAt(0);
		char[] strArray = string.toCharArray();
		if(firstOfPattern!='*' && firstOfPattern != '.'){
			if(firstOfPattern == strArray[0]){
				return stringMatching(string.substring(1), pattern.substring(1));
			}
			else{
				return false;
			}
		}
		else if(firstOfPattern == '.'){
			return stringMatching(string.substring(1), pattern.substring(1));
		}
		else if(firstOfPattern == '*' && pattern.length()>1){
			char secondOfPattern = pattern.charAt(1);
			int i = 0;
			while(strArray[i] != secondOfPattern){
				i++;
			}
			if(i >= strArray.length)
				return false;
			else{
				return stringMatching(string.substring(i+1), pattern.substring(2));
			}
		}
		return false;
	}
}

public class App {
   public static void main(String[] args) {
      System.out.println("isMatch(\"aa\", \"a\") -> " + isMatch("aa", "a"));
      System.out.println("isMatch(\"aa\", \"aa\") -> " + isMatch("aa", "aa"));
      System.out.println("isMatch(\"aaa\", \"aa\") -> " + isMatch("aaa", "aa"));
      System.out.println("isMatch(\"aa\", \"a*\") -> " + isMatch("aa", "a*"));
      System.out.println("isMatch(\"aa\", \".*\") -> " + isMatch("aa", ".*"));
      System.out.println("isMatch(\"ab\", \".*\") -> " + isMatch("ab", ".*"));
      System.out.println("isMatch(\"aab\", \"c*a*b\") -> " + isMatch("aab", "c*a*b"));
      System.out.println("isMatch(\"ccca\", \"c*a\") -> " + isMatch("ccca", "c*a"));
   }

   public static boolean isMatch(final String string, final String pattern){
      if(string == null || pattern == null || pattern.length() == 0 || pattern.substring(0,1).equals("*")){
         return false;
      }

      char[] stringChars = string.toCharArray();
      char[] patternChars = pattern.toCharArray();


      int patternIndex = 0;
      for(int i = 0; i < stringChars.length; i++){
         if(patternIndex == patternChars.length){
            return false;
         }else if(stringChars[i] == patternChars[patternIndex] || patternChars[patternIndex] == '.'){
            patternIndex++;
            continue;
         } else if(patternChars[patternIndex] == '*'){
            if(stringChars[i] == patternChars[patternIndex - 1] || patternChars[patternIndex - 1] == '.'){
               continue;
            } else {
               patternIndex++;
            }
         } else if (patternIndex+1 < patternChars.length && patternChars[patternIndex + 1] == '*') {
            patternIndex += 2;
            continue;
         } else {
            return false;
         }
      }

      return true;
   }
}

bool isMatch(const char *s, const char *p)
{
if (*s=='\0' && *p == '\0')
return true;

if (*s=='\0'|| *p=='\0')
return false;

if (*(p+1)!='*') {
if(*p==*s||*p=='.')
return isMatch(s+1, p+1);
return false;
}
else {
if (*p == '.') {
return isMatch(s, p+2) || isMatch(s+1, p)||isMatch(s+1, p+2);
}
if (*s == *p) {
return isMatch(s, p+2) || isMatch(s+1, p)||isMatch(s+1, p+2);
}

//*s not equal *p, match none
return isMatch(s, p+2);
}
}

We can do this with two stacks.

On S1, push characters from s onto it. On S2, push characters from p onto it.

Now, when we enocunter * or ., append this to the push on the stack.

Now, look at the top of the two stacks. If they match, pop both off. If they don't, then you know that there is no match. If there is '*' with a character on S2, pop from S1 however many times the character would exist. If we encounter a ., this is wildcard, so we can pop from S1 and S2 however many times we need be. The goal is to get S1 completely empty. If this happens, then we have found a match. If not, there is no match.

dynamic programming

public boolean isMatch(String s, String p) {
       int pt = 0 ;
       for (int i = 0 ; i < p.length() ;++i) {
    	   if (p.charAt(i) != '*') {
    		   pt++;
    	   }
       }
       if (pt > s.length()) {
    	   return false ;
       }    	
       boolean [][] f = new boolean[s.length() + 1][p.length() + 1];
       f[0][0] = true ;
       for (int i = 1 ; i <= p.length() ; ++i) {
    	   f[0][i] = p.charAt(i - 1) == '*' && f[0][i-1];    	   
       }
       for (int i = 1 ; i <= s.length() ; ++i) {
    	  for (int j = 1 ; j <= p.length() ; ++j) {
    		  if (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '?') {
    			  f[i][j] = f[i - 1][j - 1] ;
    		  }
    		  if (p.charAt(j - 1) == '*') {
    			  f[i][j] = f[i - 1][j - 1] || f[i - 1][j] || f[i][j - 1] ;
    		  }
    	  }
       }    
       return f[s.length()][p.length()] ;

}

public static boolean isMatch(String str, String pattern){
    String[] miniPatterns= pattern.split("[*]");
    first=true;
    for(String miniPattern:miniPatterns){
        str=isMiniMatch(str,miniPattern);
        if(str==null)
            return false;
    }
    if(pattern.charAt(pattern.length()-1)=='*')
        return true;
    
    return str.length()==0;
}

static boolean  first=true;
public static String isMiniMatch(String str, String miniPattern){
    if(str.length()<miniPattern.length())
        return null;
    int offset=0; 
    
    if (!first)
        offset=str.indexOf(miniPattern.charAt(0));
    first=false;
    for(int i=0;i<miniPattern.length();i++){
        if(miniPattern.charAt(i)!='.'){
            if(miniPattern.charAt(i)!=(str.charAt(i+offset)))
                return null;
        }
    }
    return str.substring(miniPattern.length()+offset);
}

bool isMatch(const char *s,const char *p)
{ 
	if(s == NULL || p == NULL)
		return false;
 
	int index=0;
	int patternIndex=0;
	char lastChar;
	for(patternIndex=0;patternIndex<strlen(p) && index<strlen(s);patternIndex++)
	{		
		if(p[patternIndex] == s[index])
		{
			lastChar = p[patternIndex];
			index++;
			continue;
		}

		if(p[patternIndex] == '*')
		{			
			while(index<strlen(s))
			{
				if(s[index] != lastChar)
				{
					break;
				}

				index++;
			}
		}
		else if(p[patternIndex] == '.')
		{
			lastChar = s[index];
			index++;
		}else
		{	 	
			lastChar = p[patternIndex];
		}
	}

	return (patternIndex == strlen(p) && index == strlen(s));
}

bool isMatch(const char *s,const char *p)
{ 
	if(s == NULL || p == NULL)
		return false;
 
	int index=0;
	int patternIndex=0;
	char lastChar;
	for(patternIndex=0;patternIndex<strlen(p) && index<strlen(s);patternIndex++)
	{		
		if(p[patternIndex] == s[index])
		{
			lastChar = p[patternIndex];
			index++;
			continue;
		}

		if(p[patternIndex] == '*')
		{			
			while(index<strlen(s))
			{
				if(s[index] != lastChar)
				{
					break;
				}

				index++;
			}
		}
		else if(p[patternIndex] == '.')
		{
			lastChar = s[index];
			index++;
		}else
		{	 	
			lastChar = p[patternIndex];
		}
	}

	return (patternIndex == strlen(p) && index == strlen(s));
}

int match(const char *s, const char *p)
{


if(*p=='\0' && *s=='\0')
return 0;
if(*p=='\0' || *s=='\0')
return 1;
if((*p=='.') && (*(p+1) == '*'))
return 0;
if(*p == '*')
return 0;
if(*s == *p)
return (match(s+1,p+1));
else
return 1;
}

c# Implementation

bool Match(string string, string pattern)
{
	if((pattern==null) && (string==null)  )	
		return true;
	if(pattern == "*" || pattern==string)
		return true;
	if(pattern.ElementAt(0)=="." || pattern.ElementAt(0)==string.ElementAt(0))
		return Match(string.substring(1), pattern.substring(1));
	if(pattern.ElementAt(0)=="*")
	{
		return  Match(string, pattern.substring(1)) || Match(string.substring(1), pattern) ;
	}
}

public static void main(String[] args) {		
    System.out.println("Match " + isMatchPattern("abcddd", "abcd*"));
	System.out.println("Match " + isMatchPattern("ccca", "c*a"));
	System.out.println("Match " + isMatchPattern("ab", ".*"));
	System.out.println("Match " + isMatchPattern("abcdefffffffg", "a*c..f*"));			
	System.out.println("Match " + isMatchPattern("fffffffgcdeeeeeee", "f*g..e*"));
	System.out.println("Match " + isMatchPattern("abc", "...e*"));
}

public static boolean isMatchPattern(String s, String p) {
	
	char[] cs = s.toCharArray();
	char[] cp = p.toCharArray();
	
	boolean inRep = false;
	int i = 0, j = 0;
	
	while(i < cs.length && j < cp.length) {
		if (j + 1 < cp.length) {
			if (cp[j + 1] == '*') {
				inRep = true;
			} 
		}			
		if (cs[i] == cp[j] || cp[j] == '.') {
			if (inRep && cp[j] != '.' && cp[j] != '*') {
				while(i < cs.length && j < cp.length && cs[i] == cp[j]) {
					i++;
				}
				j+=2;
				inRep = false;
			} else {
				i++;
				j++;
			}								
		} else {
			if (inRep) {
				i++;
				j++;
				inRep = false;										
			} else {
				return false;	
			}								
		}			
	}
	
	if (i < cs.length) {
		return false;
	}
			
	return true;
}

bool isMatch(const char *s, const char *p) {
    while (*p) {
        char c = *p++;
        while (*s && (*s == c || c == '.'))
            if (++s, *p != '*')
                break;
        p += *p == '*';
    }
    return !*s;
}

bool isMatch(const char *s, const char *p) {
    while (*p) {
        char c = *p++;
        while (*s && (*s == c || c == '.'))
            if (++s, *p != '*')
                break;
        p += *p == '*';
    }
    return !*s;
}

bool isMatch(const char *s, const char *p) {
    while (*p) {
        char c = *p++;
        while (*s && (*s == c || c == '.'))
            if (++s, *p != '*')
                break;
        p += *p == '*';
    }
    return !*s;

}

c++ implementation, assumes *s and *p and not null, slightly contrived to reduce lines of code

bool isMatch(const char *s, const char *p) {
    while (*p) {
        char c = *p++;
        while (*s && (*s == c || c == '.'))
            if (++s, *p != '*')
                break;
        p += *p == '*';
    }
    return !*s;
}

In C++

bool isMatch(const char *s, const char *p) {
    while (*p) {
        char c = *p++;
        while (*s && (*s == c || c == '.'))
            if (++s, *p != '*')
                break;
        p += *p == '*';
    }
    return !*s;
}

Modified Trie??

public static boolean isMatch(String str1, String str2){

if (str1.length() == 0 && str2.length() == 0)
return true;
else if (str1.length() == 0 || str2.length() == 0){
return false;
}
Stack<Character> stk1 = new Stack<Character>();
Stack<Character> stk2 = new Stack<Character>();
int i = 0;
while (i < str2.length()){
if (str2.charAt(i) == '*'){
stk2.push('*');
while (!stk1.isEmpty()){
stk2.push(stk1.pop());
}
}else{
stk1.push(str2.charAt(i));
}
i++;
}
i = str1.length()-1;
while (i >= 0){
if (!stk1.isEmpty()){
char temp2 = stk1.peek();
if ((temp2 != '.' && str1.charAt(i) == temp2) || temp2 == '.'){
stk1.pop();
}else{
return false;
}
}else{
if (!stk2.isEmpty()){
char temp = stk2.peek();
if (temp != '.' && temp != '*' && str1.charAt(i) != temp){
return false;
}else if(temp != '.' && temp != '*' && str1.charAt(i) == temp){
stk2.pop();
}else if(temp == '.'){
stk2.pop();
}
}else{
return false;
}
}
i--;
}
return true;
}

Java Stuck code

public static boolean isMatch(String str1, String str2){
		
		if (str1.length() == 0 && str2.length() == 0)
			return true;
		else if (str1.length() == 0 || str2.length() == 0){
			return false;
		}
		Stack<Character> stk1  =  new Stack<Character>();
		Stack<Character> stk2  =  new Stack<Character>();
		int i = 0;
		while (i < str2.length()){
			if (str2.charAt(i) == '*'){
				stk2.push('*');
				while (!stk1.isEmpty()){
					stk2.push(stk1.pop());
				}
			}else{
				stk1.push(str2.charAt(i));
			}
			i++;
		}
		i = str1.length()-1; 
		while (i >= 0){
			if (!stk1.isEmpty()){
				char temp2 = stk1.peek();
				if ((temp2 != '.' && str1.charAt(i) == temp2) || temp2 == '.'){
					stk1.pop();
				}else{
					return false;
				}
			}else{
				if (!stk2.isEmpty()){
					char temp  = stk2.peek();
					if (temp != '.' && temp != '*' && str1.charAt(i) != temp){
						return false;
					}else if(temp != '.' && temp != '*' && str1.charAt(i) == temp){
						stk2.pop();
					}else if(temp == '.'){
						stk2.pop();
					}
				}else{
					return false;
				}
			}
			i--;
		}
		return true;
	}

public class PatternMatching
{
  // arguments are passed using the text field below this editor
  public static void main(String[] args)
  {
    String original = "aaaab";
    String pattern = "c*a*b";
    System.out.println(isMatch(original, pattern));
  }
  
  private static boolean isMatch(String original, String pattern) {
    
    char[] originalArray = original.toCharArray();
    char[] patternArray = pattern.toCharArray();
    
    int i = 0, j = 0;
    char previousChar = '\u0000';
    
    while (i < original.length() && j < pattern.length()) {
      if (patternArray[j] == originalArray[i]) {
        previousChar = originalArray[i];
        i++;
        j++;
      }
      else if (patternArray[j] == '*') {
        if(previousChar == '.' || previousChar == originalArray[i]) 
            i++;
          else
          	j++;
      }
      else if (patternArray[j] == '.') {
        previousChar = '.';
        i++;
        j++;
      }
      else {
        i = 0;
        j++;
        previousChar = '\u0000';
      }
    }
    if (i == original.length())
    	return true;
    return false;
  }
}

public class PatternMatching
{
  // arguments are passed using the text field below this editor
  public static void main(String[] args)
  {
    String original = "aaaab";
    String pattern = "c*a*b";
    System.out.println(isMatch(original, pattern));
  }
  
  private static boolean isMatch(String original, String pattern) {
    
    char[] originalArray = original.toCharArray();
    char[] patternArray = pattern.toCharArray();
    
    int i = 0, j = 0;
    char previousChar = '\u0000';
    
    while (i < original.length() && j < pattern.length()) {
      if (patternArray[j] == originalArray[i]) {
        previousChar = originalArray[i];
        i++;
        j++;
      }
      else if (patternArray[j] == '*') {
        if(previousChar == '.' || previousChar == originalArray[i]) 
            i++;
          else
          	j++;
      }
      else if (patternArray[j] == '.') {
        previousChar = '.';
        i++;
        j++;
      }
      else {
        i = 0;
        j++;
        previousChar = '\u0000';
      }
    }
    if (i == original.length())
    	return true;
    return false;
  }
}

public class PatternMatching
{
  // arguments are passed using the text field below this editor
  public static void main(String[] args)
  {
    String original = "aaaab";
    String pattern = "c*a*b";
    System.out.println(isMatch(original, pattern));
  }
  
  private static boolean isMatch(String original, String pattern) {
    
    char[] originalArray = original.toCharArray();
    char[] patternArray = pattern.toCharArray();
    
    int i = 0, j = 0;
    char previousChar = '\u0000';
    
    while (i < original.length() && j < pattern.length()) {
      if (patternArray[j] == originalArray[i]) {
        previousChar = originalArray[i];
        i++;
        j++;
      }
      else if (patternArray[j] == '*') {
        if(previousChar == '.' || previousChar == originalArray[i]) 
            i++;
          else
          	j++;
      }
      else if (patternArray[j] == '.') {
        previousChar = '.';
        i++;
        j++;
      }
      else {
        i = 0;
        j++;
        previousChar = '\u0000';
      }
    }
    if (i == original.length())
    	return true;
    return false;
  }
}

Sample code, however we can still improvise.

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class PatternMatch {
	public void isMatch(String s, String p){
		boolean result= true;
		 Pattern pattern = Pattern.compile(p);
		Matcher matcher= pattern.matcher(s);
		result = matcher.matches();
		System.out.println(result);
	}
	public static void main(String[] args) {		
		PatternMatch pM = new PatternMatch();
		pM.isMatch("aa", "a");
		pM.isMatch("aa", "aa");
		pM.isMatch("aaa", "aa");
		pM.isMatch("aa", "a*");		
		pM.isMatch("aa", ".*");
		pM.isMatch("ab", ".*");
		pM.isMatch("aab", "c*a*b");
		pM.isMatch("ccca", "c*a");	     
 	}
}

def match(s,p):
if p=='' or s=='' :
return
matchflag=True


c=0
d=0

while c<len(s) and d<len(p):



if s[c]==p[d]:
c+=1
d+=1


elif p[d]=='.' and p[d+1]=="*" :

return matchflag


elif p[d]=='.' :
c+=1
d+=1


elif p[d]=='*':

last=p[d-1]

if last!=s[c]:
matchflag=False
return matchflag

while s[c]==last:
c+=1

if c==len(s):
return matchflag
else:
continue

d+=1
if d<len(p) and c<len(s):
if s[c]==p[d]:
c+=1
d+=1


else:
matchflag=False
return matchflag

elif s[c]!=p[d]:
matchflag=False
return matchflag


if c<len(s):
matchflag=False
return matchflag

return matchflag

print "###########################################1"
if match("ccca", "c*a") :
print "Match "

else :
print "No Match"


print "###########################################2"

if match("abc","a.*") :
print "Match "

else :
print "No Match"
print "###########################################3"

if match("aa","a") :
print "Match "

else :
print "No Match"
print "###########################################4"

if match("aa","aa") :
print "Match "

else :
print "No Match"
print "###########################################5"

if match("aaa","aa") :
print "Match "

else :
print "No Match"
print "###########################################6"


if match("aa", "a*") :
print "Match "

else :
print "No Match"
print "###########################################7"

if match("aa", ".*") :
print "Match "

else :
print "No Match"
print "###########################################8"


if match("ab", ".*") :
print "Match "

else :
print "No Match"
print "###########################################9"


if match("aab", "c*a*b") :
print "Match "

else :
print "No Match"
print "###########################################10"

if match("aab", "c*a*b") :
print "Match "

else :
print "No Match"
print "###########################################11"



if match("ccca", "c*a") :
print "Match "

else :
print "No Match"
print "###########################################12"

if match("aabbcc", "a*b*c*") :
print "Match "

else :
print "No Match"
print "###########################################"

if match("", "") :
print "Match "

else :
print "No Match"
print "###########################################"

if match("dsd", "") :
print "Match "

else :
print "No Match"
print "###########################################"

#include <iostream>
#include <string>
#include <vector>

using namespace std;

int main(){

string str = "abc";
string str2;

cin >> str2;

int i=0;
int j=0;

while(i<str.size() && j<str2.size())
{
cout << "Here" << endl;

if ((str2[j] != '.') && (str2[j] != '*') && (str2[j] != str[i]))
{
cout << "It's Not A Match" << endl;
return 0;
}

if (str2[j] == '*' && j==str2.size()-1){
cout << "Its A match" << endl;
return 0;
}


if (str[i] == str2[j] || str2[j]=='.'){

if (i==str.size()-1 && j==str2.size()-1){
cout << "Its A match" << endl;
return 0;
}

i++;
j++;
continue;
}

cout << "Before here" << endl;


if (str2[j] == '*'){
while(str2[j+1] != str[i] && i < str.size()){
i++;
if (i == str.size()){
cout << "Its Not A match" << endl;
return 0;
}
}
j++;
}

}

if(j < str2.size() && str2[j]=='*'){
cout << "It's a Match" << endl;
return 0;
}

cout << "It's not a Match" << endl;


return 0;
}

def match(string, pattern, s_pos, p_pos):
	if s_pos >= len(string) and p_pos <= len(pattern):
		return True
	if s_pos >= len(string) or p_pos >= len(pattern):
		return False
	
	p_char = pattern[p_pos]
	s_char = string[s_pos]
	if p_char == '.':
		return match(string, pattern, s_pos + 1, p_pos + 1)
	elif p_char == '*':
		prev_char = string[s_pos - 1]
		if pattern[p_pos - 1] == '.':
			prev_char = '.'
			
		while (s_pos < len(string) and (string[s_pos] == prev_char or prev_char == '.')):
			s_pos += 1
			
		return match(string, pattern, s_pos, p_pos + 1)
	else:
		if p_char != s_char:
			return False
		
		return match(string, pattern, s_pos + 1, p_pos + 1)
		
string = 'ccca'
pattern = 'c*a'
print match(string, pattern, 0, 0)