तारों की सूची में एक सामान्य स्ट्रिंग खोजें

Question

मैं इस पर बहुत करीब हूं। मुझे कल डेवलपर द्वारा एक प्रश्न पूछा गया था कि अगर मैं इसे देख सकूं।

मुझे नज़दीक लगता है, लेकिन मुझे लगता है कि यहां कुछ लोग भी चुनौती की सराहना करेंगे और मैं हार गया हूं।

अगर मैं एक List<string> जो निम्नलिखित सदस्य हैं है:

आज

सोमवार

मंगलवार

बुधवार

मैं एक वापसी स्ट्रिंग प्राप्त करना चाहते हैं day क्योंकि यह में सबसे बड़ी आम स्ट्रिंग है। यह स्थिति और स्ट्रिंग की लंबाई के बावजूद किया जाना चाहिए, बस तारों की मेज में सबसे बड़ी लंबाई सामान्य स्ट्रिंग को ढूंढना चाहते हैं।

मेरे प्रयास बुरी तरह एक सा विफल रहा है, मेरे द्वारा चुने गए:

सोमवार - मंगलवार

सोमवार - बुधवार

और फिर प्रत्येक के बीच एक 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", "दिन",

"के लिए", "ओवर ड्राफ्ट", "दा "" ay ",

" टी "," ओ "," डी "," एक "," वाई "

की गणना इस सूची में, पहली प्रविष्टि है जिसके लिए अन्य सभी तार, जिनमें शामिल है खोजने प्रवेश।

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