2
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ Does X mean any character? Do the most and best mean with the shortest Levenshtein distance? $\endgroup$ – reinierpost Oct 7 at 8:41
  • $\begingroup$ @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. $\endgroup$ – FMashiro Oct 7 at 8:44
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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.. $\endgroup$ – FMashiro Oct 8 at 8:11

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.