문자열 목록 내의 공통 문자열 찾기

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 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"

"여우", "ODA", "일",

"받는 사람", "OD", "다 ","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);