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

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

我觉得很亲密，但我认为这里的一些人也会很欣赏这个挑战，我迷失了。

如果我有一个List ，它包含以下成员：

今天

星期一

星期二

星期三

我想获得一个返回字符串day因为这是List 最大的常见字符串 。 无论位置和字符串长度如何，都应该这样做，只想在一组字符串中找到最大长度的公共字符串。

我的尝试失败了一点，我选择了：

星期一星期二

周一至周三

然后在每个之间进行Intersect 。 显然这将返回多个字符串，但是对于Monday - Wednesday你得到nday因为这是它常见的字母。

这是我的代码：

  List strs = new List(); 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 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 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

找到列表中最短的条目。

• 今天
• 星期一
• 星期二
• 星期三

所以我们使用“今天”。

在“今天”中将字符串长度的字符串列表构建到每个字符，以“最长的第一”顺序构建。

“今天”，

“户田”，“今天”，

“Tod”，“oda”，“day”，

“To”，“od”，“da”，“ay”，

“t”，“o”，“d”，“a”，“y”

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

  List words = new List { "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 parts = new List(); 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 words = new List { "Todays", "Monday", "Tuesday" }; // Sort word list by length List 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);