正则表达式用于错过字母的单词以及按顺序颠倒的两个字母

Question

我想详细说明一个涵盖以下场景的正则表达式:

搜索到的单词是"马铃薯".

如果用户搜索"potaot"(他快速键入并且"o"手指比"t"手指快,则匹配.(完成)

如果用户搜索"ptato"(他忘了一个字母),它会匹配.(完成)

凭借我对正则表达式的了解,我能够进一步发展:

 (?=[potato]{5,6})p?o?t?a?t?o?

这个问题是它匹配像"otatop"这样的反向词,这是一个有点聪明但有点bezarre,和"ooooo",这是完全不受欢迎的.所以我没有描述我不想要的东西.

我不希望重复的字母与"ooooo","ooopp"等相匹配(无法)

顺便说一句,我正在使用C#.

Answer 1

不要使用正则表达式.

最好的解决方案就是简单.只有十一种可能不精确的匹配,所以只需枚举它们:

List<string> inexactMatches = new List<string> {
  "otato", "ptato", "poato", "potto", "potao", "potat",
  "optato", "ptoato", "poatto", "pottao", "potaot"};
...
bool hasInexactMatch = inexactMatches.Contains(whatever);

输入它们需要不到一分钟的时间; 使用简单的特定解决方案,而不是尝试做一些疯狂的正则表达式,这将花费你几个小时来查找和调试.

如果你要坚持使用正则表达式,这里有一个有用的:

otato|ptato|poato|potto|potao|potat|optato|ptoato|poatto|pottao|potaot

再说一次:更简单更好.

现在,人们可能会认为你想解决这个问题,而不是"马铃薯".在这种情况下,您可能已经这么说了 - 但无论如何,我们可以提出一些简单的解决方案.

首先,让我们枚举从目标字符串中省略一个字母的所有字符串.字符串是IEnumerable<char>如此让我们解决一般问题:

static IEnumerable<T> OmitAt<T>(this IEnumerable<T> items, int i) =>
  items.Take(i).Concat(items.Skip(i + 1));

这有点粗略地列举了两次序列,但我不打算强调它.现在让我们为字符串制作一个特定的版本:

static IEnumerable<string> Omits(this string s) =>
  Enumerable
    .Range(0, s.Length)
    .Select(i => new string(s.OmitAt(i).ToArray()));

大.现在我们可以说"frob".Omits()并回来了rob, fob, frb, fro.

现在让我们进行交换.再次,首先解决一般问题:

static void Swap<T>(ref T x, ref T y)
{
    T t = x;
    x = y;
    y = t;
}

static T[] SwapAt<T>(this IEnumerable<T> items, int i)
{
    T[] newItems = items.ToArray();
    Swap(ref newItems[i], ref newItems[i + 1]);
    return newItems;
}

现在我们可以解决它的字符串:

static IEnumerable<string> Swaps(this string s) =>
    Enumerable
      .Range(0, s.Length - 1)
      .Select(i => new string(s.SwapAt(i)));

现在我们完成了:

string source = "potato";
string target = whatever;
bool match = 
  source.Swaps().Contains(target) || 
  source.Omits().Contains(target);

十分简单. 使用简单,直接,正确的算法解决一般问题,这些算法可以组成更大的解决方案.我的算法都不超过三行,很容易看出它们是正确的.