查找字符串列表中的常见字符串

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中找到）

---

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

Answer 2

发现在最短的条目名单。

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

所以我们用 “今天”。

按照“最长的第一个”顺序，在字符串长度的“今天”中向下逐个字符地建立连续字符串列表。

“今天”，

“户”， “ODAY”，

“托德”， “小田”， “天”，

“收件人”， “OD”，“DA ”， “AY”，

“T”， “O”， “d”， “A”， “Y”

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

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