Such questions are not enough. But all that I found are looking for either specific pieces in the strings, or simply matching characters. The question is this. There is a List-filled list. In this sheet you need to find the part common to all the lines. BUT! It is necessary to find not all matching characters, but the first matching part. For example:

QWERTY12345 YU QWER TY4564 F QWERGH145 QWER T777 QWE RBT

The result of this comparison should be QWE.

I tried this here.

 public static string CommonString(string first, string second) { return new string((first.Intersect(second)).ToArray()); }

But she, it seems, is looking for all the symbols that are encountered and makes agregate, and therefore does not fit.

  • And will it always coincide from the beginning of the lines? - pavel
  • Yes, in my case, it will coincide with the beginning of the lines. - Darron
  • If I have an empty string - then the common characters are zero? If there is a string of 1 character and it does not coincide with the first character of any other string, is the zero common again? - Monk
  • There will be no blank lines in the sequence. As for the single character - most likely, at least one character will match. - Darron

4 answers 4

Just compare all the first characters, then all the second, etc. until at least one does not match ...

I can write on C / C ++, C # is not mine ...

In C ++, something like

 string common(const vector<string>& sts) { for(int i = 0;;++i) for(int j = 1; j < sts.size(); ++j) if (sts[j-1][i] != sts[j][i]) return sts[0].substr(0,i); }

Update Taking into account the comments made in the comments:

 string common(const vector<string>& sts) { if (sts.size() == 0) return ""; if (sts.size() == 1) return sts[0]; for(int i = 0;;++i) { for(int j = 1; j < sts.size(); ++j) if (sts[j-1][i] != sts[j][i]) return sts[0].substr(0,i); if (sts[0][i] == 0) return sts[0]; } }
  • Comments are not intended for extended discussion; conversation moved to chat . - Nick Volynkin ♦

I do not pretend to answer, just rewrote the @Harry algorithm in C # a bit:

 string Common(List<string> sts) { if (sts.Count <= 1) throw new Exception("sts.Count <= 1"); var result = ""; for (int i = 0;; ++i) { var ok = true; for (int j = 1; j < sts.Count; ++j) { if (sts[j - 1][i] != sts[j][i]) { ok = false; break; } } if (ok == false) { result = sts[0].Substring(0, i); break; } } return result; }

ps be sure to handle exceptions when calling this method in custom code!

A little corrected, not done without Linq:

 string Common(List<string> sts) { sts = sts.Distinct().ToList(); if (sts.Count == 0) throw new Exception("sts.Count == 0"); if (sts.Count == 1) throw new Exception("sts.Count == 1"); for (int i = 0;;i++) { for (int j = 1; j < sts.Count; j++) { try { if (sts[j - 1][i] != sts[j][i]) return sts[0].Substring(0, i); } catch (IndexOutOfRangeException) { return sts[0].Substring(0, i); } } } }

The third option:

 string Common(string[] buffer) { var bufferLen = buffer.Length; if (bufferLen == 0) throw new Exception("buffer.Length == 0"); if (bufferLen == 1) throw new Exception("buffer.Length == 1"); var minStrLen = buffer.Min().Length; for (int i = 0; i < minStrLen; i++) for (int j = 1; j < bufferLen; j++) { var str1 = buffer[j - 1]; var str2 = buffer[j]; if (str1.Length > i && str2.Length > i) { if (str1[i] != str2[i]) return buffer[0].Substring(0, i); } else { return buffer[0]; } } return buffer[0]; }
  • one
    I think one of the branches does not return value - 4per
  • @ 4per, thank you, slightly corrected. It is strange that the studio did not give an error. - Align
  • one
    Hmm .. And on the lines {"a", "ab"} it does not fall? - Qwertiy ♦
  • one
    catch slow ... - Qwertiy ♦
  • one
    maxStrLen - why do we need max if we need min? - Qwertiy ♦

http://ideone.com/KgDyXk

 using System; using System.Collections.Generic; public class Test { static string Common(List<string> strs) { if (strs == null || strs.Count == 0) return ""; if (strs.Count == 1) return strs[0]; for (int i = 0; i < strs[0].Length; ++i) for (int q = 1; q < strs.Count; ++q) if (strs[q].Length == i) return strs[q]; else if (strs[q][i] != strs[q-1][i]) return strs[q].Substring(0, i); return strs[0]; } public static void Main() { Console.WriteLine("{1}: {0}", Common(new List<string>()), ""); Console.WriteLine("{1}: {0}", Common(new List<string>() { "a" }), "a"); Console.WriteLine("{1}: {0}", Common(new List<string>() { "a", "a" }), "a"); Console.WriteLine("{1}: {0}", Common(new List<string>() { "a", "ab" }), "a"); Console.WriteLine("{1}: {0}", Common(new List<string>() { "ab", "a" }), "a"); Console.WriteLine("{1}: {0}", Common(new List<string>() { "ab", "cd" }), ""); Console.WriteLine("{1}: {0}", Common(new List<string>() { "ab", "cd", "" }), ""); Console.WriteLine("{1}: {0}", Common(new List<string>() { "ab", "ab" }), "ab"); Console.WriteLine("{1}: {0}", Common(new List<string>() { "ab", "ab", "" }), ""); Console.WriteLine("{1}: {0}", Common(new List<string>() { "abacaba", "aba", "abacaba" }), "aba"); } }

    The solution does not claim to be the best, but it’s not cumbersome at all, plus it’s always nice to reduce the solution to a single LINQ request :)

     public static string FindCommonPrefix(IEnumerable<string> strings) { if (strings == null || !strings.Any()) { return string.Empty; } var prefix = strings .Aggregate((IEnumerable<char> string1, IEnumerable<char> string2) => string1.Zip(string2, (letter1, letter2) => new { Letter1 = letter1, Letter2 = letter2 }) .TakeWhile(pair => pair.Letter1 == pair.Letter2) .Select(pair => pair.Letter1)); return string.Join(string.Empty, prefix); } ... var prefix = FindCommonPrefix(new List<string> { "QWERTY12345 YU", "QWER TY4564 F", "QWERGH145", "QWER T777", "QWE RBT", }); Console.WriteLine(prefix);

    A little explanation:

    1. The casting of a string to IEnumerable<char> done in order to provide access to individual characters in a string. Unlike calling the String.ToCharArray method String.ToCharArray copying characters does not occur.

    2. The Enumerable.Aggregate method applies an aggregate function to a sequence of characters:

      • "QWERTY12345 YU", "QWER TY4564 F" → "QWER";

      • "QWER", "QWERGH145" → "QWER";

      • ...

      • "QWER", "QWE RBT" → "QWE".

    3. The Enumerable.Zip method combines characters with the same index until the end of one of the strings is reached. In this case, the method Enumerable.TakeWhile is also used, so the union takes place until one of the strings either runs out of characters or the condition of equality of characters becomes false.