c# - 在字符串列表中查找公共(public)字符串

Question

我非常接近这一点。昨天，开发人员问我是否可以看一下这个问题。

我感觉很亲近，但我认为这里的一些人也会喜欢挑战，而我迷路了。

如果我有一个 List<string>其中有以下成员:

Today

Monday

Tuesday

Wednesday

我想得到一个返回字符串day因为这是 List<string> 中的最大的公共(public)字符串 .这应该与位置和字符串长度无关地完成，只是想在一大堆字符串中找到最大长度的公共(public)字符串。

我的尝试有点惨败，我选择了:

Monday - Tuesday

Monday - Wednesday

然后做了一个Intersect每个之间。显然这会返回多个字符串，但是对于 Monday - Wednesday你得到 nday因为这是它常用的字母。

这是我的代码:

  List<string> strs = new List<string>();
  strs.Add("Monday");
  strs.Add("Tuesday");
  strs.Add("Wednesday");

  var v = strs.SelectMany((day, i) => strs.Select((day2, j) => new
  {
    iDay = i,
    Day = day,
    iDay2 = j,
    Day2 = day2
  })).Where(x => x.iDay != x.iDay2).Select(x => new string(x.Day.Intersect(x.Day2).ToArray()));

谁有好的、简洁的解决方案？

注意

不一定是 LINQ

如果没有一个共同的字符串，返回null或空字符串。

Answer 1

这比我的第一种方法(删除线)效果更好。

您可以使用以下扩展来获取列表中最短字符串的所有子字符串(为了提高效率):

public static IEnumerable<string> getAllSubstrings(this string word)
{
    return from charIndex1 in Enumerable.Range(0, word.Length)
           from charIndex2 in Enumerable.Range(0, word.Length - charIndex1 + 1)
           where charIndex2 > 0
           select word.Substring(charIndex1, charIndex2);
}

• 现在按长度(最长的在前)对这些子串进行排序
• 查看所有其他字符串(不包括字符串本身，因为该测试是多余的)是否包含该子字符串(如果一个字符串不包含给定子字符串，Enumerable.All 立即返回)
• 如果一个字符串出现在所有其他字符串中，则您找到了最长的公共(public)子字符串
• 否则重复直到检查完所有子字符串(如果没有找到公共(public)字符串)

---

string shortest = list.OrderBy(s => s.Length).First();
IEnumerable<string> shortestSubstrings = shortest
    .getAllSubstrings()
    .OrderByDescending(s => s.Length);
var other = list.Where(s => s != shortest).ToArray();
string longestCommonIntersection = string.Empty;
foreach (string subStr in shortestSubstrings)
{
    bool allContains = other.All(s => s.Contains(subStr));
    if (allContains)
    {
        longestCommonIntersection = subStr;
        break;
    }
}

DEMO