Stringa inversa alla corrispondenza del pattern

Question

Ho un elenco di schemi e devo trovare il modello che corrisponda di più a una stringa di input. Cioè:

Modelli:

[
    'AB1XXX',
    'AB2XXX',
    'ABXXXX-0080',
    'BC1XXX',
    'BC15XX'
]

Il X Il carattere nei motivi è riservato come il wildcard o don't care carattere. Può essere qualsiasi singolo carattere alfanumerico.

Ho quindi un input, cioè: AB1100. In questo caso mi aspetto il modello AB1XXX essere la migliore partita. Tuttavia, se ricevo un input AB1100-0080 Mi aspetto ABXXXX-0080 Per essere la migliore corrispondenza per l'input dato.

Attualmente uso un trie per trovare il modello di abbinamento, ma non funziona davvero per l'esempio dato in quanto non riesce a trovare una partita una volta arrivato -0080.

Best match può essere visto come "la distanza di levenshtein più breve con la minima quantità di X caratteri usati ".

Esiste un algoritmo noto che potrei implementare o dovrei attenersi all'implementazione di un algoritmo a distanza Levenshtein?