I have a list of patterns, and I need to find the pattern that matches an input string the most. I.e.:
[ 'AB1XXX', 'AB2XXX', 'ABXXXX-0080', 'BC1XXX', 'BC15XX' ]
X character in the patterns is reserved as the
don't care character. It can be any single alphanumeric character.
I then get an input, i.e.:
AB1100. In this case I expect the pattern
AB1XXX to be the best match.
However, if I get an input
AB1100-0080 I expect
ABXXXX-0080 to be the best match for the given input.
I currently use a Trie to find the matching pattern, but it doesn't really work for the given example as it either can't find a match once it gets to
Best match can be seen as "shortest Levenshtein distance with the least amount of X characters used".
Is there a known algorithm I could implement or should I stick to implementing a Levenshtein distance algorithm?