7

我非常接近这一点。我昨天收到一个开发人员向我提出的问题，如果我可以看看这个。

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

如果我有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或空字符串。

4

2 回答 2

7

这比我的第一种方法（删除）更好。

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

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;
    }
}

演示

于 2012-11-22T09:28:01.453 回答
3

查找列表中最短的条目。

  • 今天
  • 周一
  • 周二
  • 周三

所以我们使用“今天”。

在“Today”中构建一个连续字符的字符串列表，将字符串的长度向下到每个字符，以“最长的优先”顺序。

“今天”，

“户田”、“今天”、

“Tod”、“oda”、“day”、

“到”、“od”、“da”、“ay”、

“今天”

枚举这个列表，找到所有其他字符串都包含该条目的第一个条目。

        List<string> words = new List<string> { "Today", "Monday", "Tuesday", "Wednesday" };

        // Select shortest word in the list
        string shortestWord = (from word in words
                            orderby word.Length
                            select word).First();

        int shortWordLength = shortestWord.Length;

        // Build up the list of consecutive character strings, in length order.
        List<string> parts = new List<string>();
        for (int partLength = shortWordLength; partLength > 0; partLength--)
        {
            for (int partStartIndex = 0; partStartIndex <= shortWordLength - partLength; partStartIndex++)
            {
                parts.Add(shortestWord.Substring(partStartIndex, partLength));
            }
        }
        // Find the first part which is in all the words.
        string longestSubString = (from part in parts where words.All(s => s.Contains(part)) select part).FirstOrDefault();

       // longestSubString is the longest part of all the words, or null if no matches are found.

编辑

多想一点，就可以优化一点。

您无需建立零件列表 - 只需在生成每个零件时对其进行测试。此外，通过按长度顺序对单词列表进行排序，您总是首先测试最短的字符串以更快地拒绝候选部分。

        string longestSubString = null;

        List<string> words = new List<string> { "Todays", "Monday", "Tuesday" };

        // Sort word list by length
        List<string> wordsInLengthOrder = (from word in words
                                           orderby word.Length
                                           select word).ToList();

        string shortestWord = wordsInLengthOrder[0];
        int shortWordLength = shortestWord.Length;

        // Work through the consecutive character strings, in length order.
        for (int partLength = shortWordLength; (partLength > 0) && (longestSubString == null); partLength--)
        {
            for (int partStartIndex = 0; partStartIndex <= shortWordLength - partLength; partStartIndex++)
            {
                string part = shortestWord.Substring(partStartIndex, partLength);

                // Test if all the words in the sorted list contain the part.
                if (wordsInLengthOrder.All(s => s.Contains(part)))
                {
                    longestSubString = part;
                    break;
                }
            }

        }

        Console.WriteLine(longestSubString);
于 2012-11-22T09:30:31.457 回答