在字符串列表中查找公共字符串

Question

我非常接近这一点.如果我能看一下,我昨天有一个问题向我提出了一个问题.

我觉得很亲密,但我觉得这里的一些人也很欣赏这个挑战,我迷失了.

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

今天

星期一

星期二

星期三

我希望得到一个返回的字符串day,因为这是最大的常见字符串中List<string>.无论位置和字符串长度如何,都应该这样做,只想在一大串字符串中找到最大长度的公共字符串.

我的尝试失败了一点,我选择了:

星期一星期二

周一至周三

然后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);
}

• 现在订购这些子串Length(最长的)
• 查看所有其他字符串(由于该测试是冗余的,不包括字符串本身)包含该子字符串(Enumerable.All如果一个字符串不包含给定的子字符串,则立即返回)
• 如果所有其他字符串中出现一个字符串,则表示找到了最长的公共子字符串
• 否则重复一遍,直到你检查了所有子串(如果没有找到常见的字符串)

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