CareerCup

I think that the "catch" here is to implement the match function, so solutions that uses built-in match functions like - grep,contains etc misses the point (in my opinion).

And the objective, as I see it is to find an efficient solution for the matching function.

We can go char by char as stated in a few solutions above and simply compare, that will have us compare all the characters in the input strings with all the characters in the pattern.

I would go at it in a bit different approach and compare in bulks, by using a hashing function on the pattern.

The idea is to calculate the hash (for example sum(2^ASCII(char))) value of the searched pattern and then calculate the same hash value for each "bulk" in the input string. We then can use the notion that the hash value of the N chars we calculated can be composed of hash(N-1) + hash(N), so by calculating this first, to calculate the next hash we only need to subtract N-len(pattern) and add N+1 hash to get the new hash for the comparison.
And only if the hash matches we can verify by matching with comparison of the string.

Complexity of the above is O(n) , since we go over the entire input once and do 2 calculations - O(1) , for each comparison.

sadasd

We can use shell script (If working environment is Linux). This is very simple & efficient. You can easily parse through numerous strings.

str_list=( "crane" "grain" "Insane" )
for i in "${str_list[@]}"
do
echo "$i" | grep '.*an.*'
done

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        NSArray<NSString *> *strings = @[@"crane", @"drain", @"refrain"];
        NSPredicate *predicate = [NSPredicate predicateWithFormat:@"SELF CONTAINS[cd] 'an'"];
        
        NSArray *result = [strings filteredArrayUsingPredicate:predicate];
        NSLog(@"%@", [result firstObject]);
    }
    return 0;
}

This is how I would do this, I don't know if it's "Efficient"

str_list=( "crane" "grain" "Insane" )
for i in "${str_list[@]}"
do
echo "$i" | grep '.*an.*'
done

How about some algorithm instead of regex matching?

private static boolean isMatch(String pattern, String word) {
        boolean match = false;
        if(!pattern.contains("*")){
            return word.contains(pattern);
        }
        else{
            char[] chArr = pattern.toCharArray();
            boolean isprevW  = false;
            boolean isnextW = false;
            int patternindex = 0;
            int wordindex = 0;
            char[] wArr = word.toCharArray();
            boolean matchchar = false;
            
            while(patternindex < chArr.length && wordindex < wArr.length){
                if(chArr[patternindex] == '*'){
                    isprevW = true;
                    patternindex++;
                    continue;
                }
                if(isprevW || isnextW){
                    if(chArr[patternindex] == wArr[wordindex]){
                        patternindex++;
                        if(isprevW)isprevW = false;
                        if(isnextW)isnextW = false; 
                        wordindex++;
                        match = true;
                        matchchar = true;
                    }
                    else{
                        wordindex++;
                        match = false;
                    }
                }
                else{
                    if(chArr[patternindex] == wArr[wordindex]){
                        patternindex++;
                        wordindex++;
                        match = true;
                        matchchar = true;
                    }
                    else{
                       if(matchchar){
                           return false;
                       }
                       if(patternindex+1 < chArr.length){
                           if(chArr[patternindex+1] == '*'){
                               isnextW = true;
                               wordindex++;
                           }
                           else{
                               return false;
                           }
                       }
                    }
                }                
            }
        }
        return match;
    }

private static boolean isMatch(String pattern, String word) {
        boolean match = false;
        if(!pattern.contains("*")){
            return word.contains(pattern);
        }
        else{
            char[] chArr = pattern.toCharArray();
            boolean isprevW  = false;
            boolean isnextW = false;
            int patternindex = 0;
            int wordindex = 0;
            char[] wArr = word.toCharArray();
            boolean matchchar = false;
            
            while(patternindex < chArr.length && wordindex < wArr.length){
                if(chArr[patternindex] == '*'){
                    isprevW = true;
                    patternindex++;
                    continue;
                }
                if(isprevW || isnextW){
                    if(chArr[patternindex] == wArr[wordindex]){
                        patternindex++;
                        if(isprevW)isprevW = false;
                        if(isnextW)isnextW = false; 
                        wordindex++;
                        match = true;
                        matchchar = true;
                    }
                    else{
                        wordindex++;
                        match = false;
                    }
                }
                else{
                    if(chArr[patternindex] == wArr[wordindex]){
                        patternindex++;
                        wordindex++;
                        match = true;
                        matchchar = true;
                    }
                    else{
                       if(matchchar){
                           return false;
                       }
                       if(patternindex+1 < chArr.length){
                           if(chArr[patternindex+1] == '*'){
                               isnextW = true;
                               wordindex++;
                           }
                           else{
                               return false;
                           }
                       }
                    }
                }                
            }
        }
        return match;
    }

public static void findWordsByPattern (String[] inputStrings, String pattern)
    {
        String regex = pattern.replace("*", ".*");
        for (String s: inputStrings)
        {
            if (Pattern.matches(regex, s))
            {
                System.out.println(s);
            }
        }
    }

Scala

object PatternMatch extends App {

  println(pmatch("*an*", List("crane", "drain", "refrain")))

  def pmatch(p: String, strings: List[String]): List[String] = {
    strings.filter { str =>
      var si = 0
      var pi = 0
      var hit = false // set to true if we hit a last * in the pattern
      while (si < str.length && pi < p.length && !hit) {
        if (p(pi) == '*') {
          if (pi < p.length - 1 && p(pi + 1) == str(si)) {
            pi += 1
          } else if (pi == p.length - 1) {
            pi += 1
            hit = true
          } else {
            si += 1
          }
        } else if (p(pi) == str(si)) {
          pi += 1
          si += 1
        } else {
          pi = 0
          si += 1
        }
      }
      // the full pattern was matched
      pi == p.length ||
        // allows * to match empty character as the final character in the pattern
        (pi == p.length - 1 && p.last == '*')
    }
  }

}

public static String getMatchingWordFromList (List<String> inputList,String pattern) {

        String output = "";
        char[] patternArray = pattern.toCharArray();
        char[] realCharsArray = new char[patternArray.length -2];

        for(int i=1;i<patternArray.length-1;i++) {
            realCharsArray[i-1] = patternArray[i];
        }

        for(String input: inputList) {
            int k=0;
            char[] inputArray = input.toCharArray();
            for(int i=0;i<inputArray.length;i++){
                if(i!=inputArray.length-1 && inputArray[i]==realCharsArray[k] && inputArray[i+1]==realCharsArray[k+1]) {
                    //return input; but since not a good practice
                    output = input;
                    break;
                }
            }
            if(output!=""){
                break;
            }
        }

        return output;

}

public static String getMatchingWord(List<String> inputList,String pattern) {
        final String newPattern = pattern.replace("*",".*");
        return inputList.stream().filter(input-> input.matches(newPattern)).findAny().get();

}

public static void main(String args[])
    {
       
          String pattern="*an*";
        String enPattern=encodeString(pattern);
          String word="xyanxvsdanf";
        String enWord=encodeString(word);
        
        System.out.println(enPattern+" "+enWord);
     
        
        int v1=Integer.parseInt(enPattern);
        int v2=Integer.parseInt(enWord);
        System.out.println(" % :"+ v2%v1);
        if(v2%v1 !=0){
        System.out.println("not matched");
        }  else {
              System.out.println(" matched");
        }      
        
    }

    static String encodeString(String x){
    
        String output="";
        for(int i=0;i<x.length();i++){
         
            
            // *an* == 0110
            char c=x.charAt(i);
            if(c=='n'|| c=='a'){
                output +="1";
            } else {
            output +="0";
            }
        }
        return output;
}