Find a match, any match. You will be given very simple patterns. But, how fast can you come up with a solution when you are not allowed to use your regexp library? And yes, you might find this in your next interview.

Problem

Input. A set of words and a set of patterns. Each word and each pattern is given in a line by itself. Words and patterns are separated by character #. In patterns, the character period . matches any character. The input is terminated by EOF.

Output. For each pattern, write in a single line the pattern, a space, and true if the pattern matches a word or false if it does not. Output patterns in the order you read them.

Example

Input

coin
coins
does
dork
why
work
#
coin
coins
c
co
coi
coins
coins.
.coins
does
d
do
doe
.oes
d.es
do.s
doe.
w..
w...
w....

Output

coin true
coins true
c false
co false
coi false
coins true
coins. false
.coins false
does true
d false
do false
doe false
.oes true
d.es true
do.s true
doe. true
w.. true
w... true
w.... false

Solution

Have you heard about tries? Use them maybe?

Here is a Ruby implementation.

class Hash

def save_word w
h = self
w.chars.each do |l|
h[l] = {} if not h[l]
h = h[l]
end
h[:eow] = true
end

def word_exists? w
h = self
w.chars.each_with_index do |l, i|
if l == '.'
return h.any? { |k,v| k != :eow and v.word_exists? w[i+1..-1] }
elsif not h[l]
return false
end
h = h[l]
end
return !!h[:eow]
end

end

def main
words = {}
while true
w = readline.strip
break if w == '#'
words.save_word w
end
while true
begin
p = readline.strip
rescue EOFError => ex
break
end
puts "#{p} #{words.word_exists? p}"
end
end

main

Want to read more?

I love to explain and answer questions on programming problems, the kind you find in coding interviews. I publish a new programming problem and its solution every Sunday. Did I mention that I love to answer questions?

If you would like to get the latest problem + solution, subscribe to the newsletter or subscribe via RSS. You can also follow me on Twitter, GitHub, and LinkedIn.

Comments