CareerCup

build a trie from the file
traverse the trie based on the pattern
if it is specific character, traverse the edge of that character
if it is _, traverse all edges

Well there are a few clarifications needed -
How big is the file?
Are the strings in file sorted?
Does "_" mean single character or multiple characters?

If big file and strings are not sorted and we are using this function a lot then it makes sense to make a suffix tree like structure.
If sorted then just need to reach that point using some variation of binary search.
If small file then maybe even using brute force way of searching may be benificial.

how many _ are possible?

Does underscore ('_') imply one character, or can it be multiple characters, including no character?

If the former, then scan the file for all 4 character words starting with H, having L as the 3rd character.

Building a trie will be rather expensive, not to mention that it may not all fit into memory in the first place. Building a distributed trie is possible to workaround this, but that infrastructure investment better be worth the returns on it.

Python Example using RegEx:

import re
all_words = ["HELL", "HILL", "HELP", "HALF", "NINE", "HELLO"] # Sample Words

def findMatches (search_string):
  return [x for x in all_words if re.match (re.sub ("_", ".", search_string) + "$", x)]

matches = findMatches ("H_L_")
print matches

sd

{ String str = getString();
String []strarr = {"HELL", "HILL", "HELP", "HALF", "NINE", "HELLO"};

str = str.replace("_",".{1}");
str = "^" + str + "$";
System.out.println(str);

for(int i = 0; i<strarr.length; i++)
{
if(strarr[i].matches(str))
System.out.println(strarr[i]);
}
}

Using Python
words=['help','hell','bug','hale','gale']
s="h_l_"

for w in words:
if len(w)!=len(s):
print '%s does\'t match'%w
else:
match=True
for i in range(len(s)):
if s[i]=='_':
continue
else:
if s[i] != w[i]:
match=False
break
if match:
print '%s matches'%w
else:
print '%s dosn\'t match'%w

Scala:

Assuming the words have been read into a List:

def getPossibleSolns(words: List[String],r: Set[String]): Set[String] = words match {
 case Nil => r
 case head :: tail => head.toList match {
  case 'H' :: _ :: 'L' :: _ => getPossibleSolns(tail,r+(head))
  case _ => getPossibleSolns(tail,r)
 }
}


val xs = List("HOW","WHAT", "HELP", "WHERE", "HELD","HOW","HELL")

val r = getPossibleSolns(xs,Set())

scala> val r = getPossibleSolns(xs,Set())
r: Set[String] = Set(HELP, HELD, HELL)

We can use shell scripting... Such kind of pattern searching is much easier in scripting language.