Implement a fuzzy string matching, finding all matching strings in an array of strings. A string is considered matching, if all characters from the search string are found in the string in the same order. E.g. search string "md" should match string "Something redundant".

Question

Sigiloso · Accepted Answer

First optimize the searched array of strings by turning each string into a character path tree (i.e. each character should have links to the characters you can get next from it). Do collapsing/reusing same paths (subtrees) to save memory and CPU. Actual searching is very easy - for each string in the array merely follow the path according to the characters of the string you're searching by.

Procore Technologies

Pergunta de entrevista da empresa Procore Technologies

Resposta da entrevista

Empresas seguidas

Buscas de vagas