2
$\begingroup$

I need to design a data structure to which I can efficiently add new words(Strings) and search for an existing word. Also, the search word can contain . in it which can match any character. For eg. if I add strings "abcd" and "abed" then search for "ab.d" should return me both of them.

I tried to tackle this using prefix Tries. It works fine for normal string search(without dot) but for dot I have to search for every child of a node. Is there a more efficient way of solving this problem?

$\endgroup$
2
$\begingroup$

This problem was considered in the following papers:

See also String matching for wildcard-based records, Given a set of string patterns, find which ones match a particular string, https://cstheory.stackexchange.com/q/36913/5038.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.