I have a list of patterns, and I need to find the pattern that matches an input string the most. I.e.:
Patterns:
[
'AB1XXX',
'AB2XXX',
'ABXXXX-0080',
'BC1XXX',
'BC15XX'
]
The X
character in the patterns is reserved as the wildcard
or 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 -0080
.
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?
X
mean any character? Do the most and best mean with the shortest Levenshtein distance? $\endgroup$X
s" I'll edit my post in a minute to clear it up. $\endgroup$