c# - Find a common string within a list of strings

Question

I'm very close on this. I got a question posed to me yesterday by a developer if I could have a look at this.

I feel close, but I think some people here would appreciate the challenge too and I am lost.

If I have a List<string> which has the following members:

Today

Monday

Tuesday

Wednesday

I want to get a return string day because this is the largest common string in the List<string>. This should be done irrespective of position and string length, just want to find the largest length common string in a host of strings.

My attempt failed a bit miserably, I selected:

Monday - Tuesday

Monday - Wednesday

And then did an Intersect between each. Obviously this would return multiple strings, however for Monday - Wednesday you get nday because that is what letters it has common.

Here is my code:

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

Anybody have a nice and neat solution?

NOTE

It doesn't have to be LINQ

If there isn't a common string, return null or empty string.

Answer 1

This works better than my first approach(striked out).

You can use following extension to get all substrings of the shortest string in the list(for efficiency):

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

• now order these substrings by Length(longest first)
• look if all other strings(excluding the string itself because that test is redundant) contain that substring (Enumerable.All returns immediately if one string doesn't contain a given substring)
• if one string appears in all others you have found the longest common substring
• otherwise repeat that until you've checked all substrings(if no common string was found)

---

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