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?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Does X mean any character? Do the most and best mean with the shortest Levenshtein distance? $\endgroup$
    – reinierpost
    Oct 7, 2019 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$
    – Florian Humblot
    Oct 7, 2019 at 8:44

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
1
  • $\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$
    – Florian Humblot
    Oct 8, 2019 at 8:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.