La correspondance de la chaîne inversée à la correspondance

Question

J'ai une liste de modèles et j'ai besoin de trouver le motif qui correspond le plus à une chaîne d'entrée. C'est à dire:

Motifs:

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

La X Le caractère dans les motifs est réservé comme le wildcard ou don't care personnage. Il peut s'agir de n'importe quel caractère alphanumérique unique.

J'obtiens alors une entrée, c'est-à-dire: AB1100. Dans ce cas, je m'attends au modèle AB1XXX être le meilleur match. Cependant, si j'obtiens une entrée AB1100-0080 Je m'attends à ABXXXX-0080 pour être le meilleur match pour l'entrée donnée.

J'utilise actuellement un trie pour trouver le modèle de correspondance, mais cela ne fonctionne pas vraiment pour l'exemple donné car il ne peut pas trouver de correspondance une fois qu'il arrive -0080.

Best match peut être considéré comme "la distance la plus courte de Levenshtein avec le moins de X caractères utilisés ".

Y a-t-il un algorithme connu que je pourrais implémenter ou devrais-je m'en tenir à la mise en œuvre d'un algorithme de distance Levenshtein?