检查一个字符串是否包含与其他字符串的 Levenshtein 距离为 1 的子字符串
Check if one string includes a substring with Levenshtein distance of 1 from other string
我的问题是我们希望我们的用户输入这样的代码：
639195-EM-66-XA-53-WX 在输入的某处，因此结果可能如下所示：The code is 639195-EM-66-XA-53-WX, let me in。如果他们在代码中犯了一个小错误（Levenshtein 距离为 1），我们仍然希望匹配字符串。例如 The code is 739195-EM-66-XA-53-WX, let me in。 （代码首字母6改为7）
即使用户跳过破折号，算法也应该匹配，并且应该忽略 lowercase/uppercase 个字母。这些要求很容易满足，因为我可以删除所有破折号并执行 to_uppercase.
是否有类似的算法？
生成与原始代码距离为 1 的所有字符串在计算上非常昂贵。
我也在考虑使用 Levenshtein 距离之类的东西，但忽略了用户在第二个字符串中添加的缺失字母，但这会允许代码中间出现错误的字母。
在用户输入中搜索代码似乎好一点，但仍然不是很干净。
我有一个解决方案的想法，也许这对你来说已经足够了：
正如您所说，首先删除破折号并将所有内容设为大写（或小写）：
句子：THE CODE IS 639195EM66XA53WX, LET ME IN
代码：639195EM66XA53WX
在中间拆分代码（c1和c2），因为Levenshtein距离为1意味着只能有一个错误（单个字符的插入，删除或替换），所以c1或c2之一必须如果代码出现在句子中且只有 1 个或更少的错误，则匹配。在中间拆分，因为代码的两个子字符串越长，您应该得到的匹配越少：
c1: 639195EM
c2: 66XA53WX
现在尝试在你的句子中找到 c1 和 c2，如果你找到匹配，那么你必须在句子中向前（c1 匹配）或向后（c2 匹配）检查缺失的 Levenshtein 距离部分为 1 或更少。
因此在您的示例中，您会找到 c2 然后：
- 设置指向 c1 的最后一个字符和匹配前字符的指针。
- 当字符相同时将两个指针都减 1（在两个字符串中向后移动）。
如果您可以通过这种方式完全使用 c1，那么您就找到了一个精确匹配（Levenshtein 距离为 0）。
否则尝试编辑距离为 1 的 3 种可能性：
只将c1的指针向后移动，看其余是否匹配（删除）
只把句子的指针向后移动，看其余是否匹配（插入）。
将两个指针向后移动，看看其余指针是否匹配（替换）。
如果其中一个成功，则您找到了 Levenshtein 距离为 1 的匹配项，否则距离更高。
我的问题是我们希望我们的用户输入这样的代码：
639195-EM-66-XA-53-WX 在输入的某处，因此结果可能如下所示：The code is 639195-EM-66-XA-53-WX, let me in。如果他们在代码中犯了一个小错误（Levenshtein 距离为 1），我们仍然希望匹配字符串。例如 The code is 739195-EM-66-XA-53-WX, let me in。 （代码首字母6改为7）
即使用户跳过破折号，算法也应该匹配，并且应该忽略 lowercase/uppercase 个字母。这些要求很容易满足，因为我可以删除所有破折号并执行 to_uppercase.
是否有类似的算法？
生成与原始代码距离为 1 的所有字符串在计算上非常昂贵。
我也在考虑使用 Levenshtein 距离之类的东西，但忽略了用户在第二个字符串中添加的缺失字母，但这会允许代码中间出现错误的字母。
在用户输入中搜索代码似乎好一点，但仍然不是很干净。
我有一个解决方案的想法，也许这对你来说已经足够了：
正如您所说，首先删除破折号并将所有内容设为大写（或小写）：
句子：THE CODE IS 639195EM66XA53WX, LET ME IN
代码：639195EM66XA53WX
在中间拆分代码（c1和c2），因为Levenshtein距离为1意味着只能有一个错误（单个字符的插入，删除或替换），所以c1或c2之一必须如果代码出现在句子中且只有 1 个或更少的错误，则匹配。在中间拆分，因为代码的两个子字符串越长，您应该得到的匹配越少：
c1: 639195EM
c2: 66XA53WX
现在尝试在你的句子中找到 c1 和 c2，如果你找到匹配，那么你必须在句子中向前（c1 匹配）或向后（c2 匹配）检查缺失的 Levenshtein 距离部分为 1 或更少。
因此在您的示例中，您会找到 c2 然后：
- 设置指向 c1 的最后一个字符和匹配前字符的指针。
- 当字符相同时将两个指针都减 1（在两个字符串中向后移动）。
如果您可以通过这种方式完全使用 c1，那么您就找到了一个精确匹配（Levenshtein 距离为 0）。
否则尝试编辑距离为 1 的 3 种可能性：
只将c1的指针向后移动，看其余是否匹配（删除）
只把句子的指针向后移动，看其余是否匹配（插入）。
将两个指针向后移动，看看其余指针是否匹配（替换）。
如果其中一个成功，则您找到了 Levenshtein 距离为 1 的匹配项，否则距离更高。