# reverse string to pattern matching

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?

• Does X mean any character? Do the most and best mean with the shortest Levenshtein distance? – reinierpost Oct 7 '19 at 8:41
• @reinierpost yes, sorry, X is the wildcard, so it can be any character. "the most" or "best" would mean "with the shortest levenshtein distance and with the least Xs" I'll edit my post in a minute to clear it up. – FMashiro Oct 7 '19 at 8:44

## 1 Answer

The Shortest Levenshtein's Distance should be good enough. See if this Matching Wildcards Wikipedia page can be of help.

• Thanks, I ended up expanding my Trie implementation with a full-search which returns all matches. Then I added a levenshtein function to find the "best" match out of the matches that the Trie retuned.. – FMashiro Oct 8 '19 at 8:11