एन स्ट्रिंग

Question

के लिए सबसे लंबा आम उपसर्ग अधिकतम लंबाई मीटर की एन स्ट्रिंग दिया गया। हम उनमें से कम से कम दो तारों द्वारा साझा किए जाने वाले सबसे लंबे आम उपसर्ग को कैसे पा सकते हैं?

उदाहरण: [ 'फूल', 'प्रवाह', 'नमस्ते', 'बेड़ा']

उत्तर: fl

मैं सभी स्ट्रिंग के लिए एक Trie के निर्माण के बारे में सोच रहा था और फिर गहरी जाँच नोड (सबसे लंबे समय तक संतुष्ट) कि दो/दो से अधिक सबस्ट्रिंग्स (सामान्यता को संतुष्ट करता है) तक शाखाएं। यह ओ (एन * एम) समय और स्थान लेता है। क्या यह

Answer 1

करने का एक बेहतर तरीका है, मैं उन्हें सॉर्ट करूंगा, जो आप n lg n समय में कर सकते हैं। फिर आम उपसर्ग वाले किसी भी तार एक दूसरे के बगल में होंगे। असल में आप उस सूचकांक को रखने में सक्षम होना चाहिए जिस पर आप वर्तमान में देख रहे हैं और एक बहुत तेज़ गणना के लिए अपना रास्ता कम करें।

Answer 2

trie का उपयोग करके इस समस्या का समाधान O(|S|*n) है। [n तार की संख्या, S है सबसे लंबे समय तक स्ट्रिंग है]

(1) put all strings in a trie 
(2) do a DFS in the trie, until you find the first vertex with more then 1 "edge". 
(3) the path from the root to the node you found at (2) is the longest commin prefix. 

[बड़ा हे संकेतन के मामले में] कोई संभव तेजी से समाधान नहीं है तो यह, सबसे खराब स्थिति में, अपने सभी तार समान हैं - और आपको यह जानने के लिए उन सभी को पढ़ने की जरूरत है।

Answer 3

मेरे अन्य जवाब से एक पूरी तरह से अलग जवाब के रूप में ...

आप कर सकते हैं, एक पास, बाल्टी हर स्ट्रिंग इसके पहले अक्षर के आधार पर के साथ।

एक और पास के साथ आप प्रत्येक बाल्टी को इसके बाद के बाद क्रमबद्ध कर सकते हैं। (यह मूलांक तरह है, जो O(n*m), और प्रत्येक पास के साथ O(n) है के रूप में जाना जाता है।) यह आप के 2.

एक आधारभूत उपसर्ग आप सुरक्षित रूप से आपके डेटासेट से है कि 2 का एक उपसर्ग की जरूरत नहीं है किसी भी तत्व को हटा सकते हैं देता है।

आप p के साझा उपसर्ग के बिना तत्वों को हटाने, pm दृष्टिकोण के रूप में, रेडिक्स सॉर्ट जारी रख सकते हैं।

यह आपको O(n*m) समय देगा जो त्रिभुज दृष्टिकोण करता है, लेकिन हमेशा त्रिभुज से तेज़ होगा क्योंकि त्रिभुज प्रत्येक स्ट्रिंग में प्रत्येक चरित्र को देखना चाहिए (क्योंकि यह संरचना में प्रवेश करता है), जबकि यह दृष्टिकोण केवल प्रति स्ट्रिंग के 2 वर्णों को देखने की गारंटी है, जिस बिंदु पर यह डेटासेट का अधिकतर हिस्सा खींचता है।

सबसे खराब मामला अभी भी है कि प्रत्येक स्ट्रिंग समान है, यही कारण है कि यह एक ही बड़ी ओ नोटेशन साझा करता है, लेकिन सभी मामलों में तेज़ होगा क्योंकि किसी भी "गैर-बुरे मामले" के बाद से कम तुलना का उपयोग करने की गारंटी है ऐसे पात्र हैं जिन्हें कभी भी देखने की आवश्यकता नहीं है।

Answer 4

ट्राई का उपयोग क्यों करें (जो ओ (एमएन) समय और ओ (एमएन) स्पेस लेता है, केवल मूल ब्रूट फोर्स मार्ग का उपयोग करें। पहला लूप, मिनीस्ट्रा के रूप में सबसे छोटी स्ट्रिंग पाएं, जो ओ (एन) समय लेता है, दूसरा लूप, इस minStr के साथ एक करके एक की तुलना करें, और एक वेरिएबल रखें जो minStr के सही सूचकांक को इंगित करता है, यह लूप ओ (एमएन) लेता है जहां मीटर सभी तारों की सबसे छोटी लंबाई है।कोड, नीचे की तरह है

public String longestCommonPrefix(String[] strs) { 
    if(strs.length==0) return ""; 
    String minStr=strs[0]; 

    for(int i=1;i<strs.length;i++){ 
     if(strs[i].length()<minStr.length()) 
      minStr=strs[i]; 
    } 
    int end=minStr.length(); 
    for(int i=0;i<strs.length;i++){ 
     int j; 
     for(j=0;j<end;j++){ 
      if(minStr.charAt(j)!=strs[i].charAt(j)) 
       break; 
     } 
     if(j<end) 
      end=j; 
    } 
    return minStr.substring(0,end); 
} 

Answer 5

public String longestCommonPrefix(String[] strs) { 

    if (strs == null || strs.length == 0) 
     return ""; 

    char[] c_list = strs[0].toCharArray(); 
    int len = c_list.length; 
    int j = 0; 
    for (int i = 1; i < strs.length; i++) { 
     for (j = 0; j < len && j < strs[i].length(); j++) 
      if (c_list[j] != strs[i].charAt(j)) 
      break; 
     len = j; 
    } 

    return new String(c_list).substring(0, len); 

} 

Answer 6

ऐसा होता है कि बाल्टी प्रकार (मूलांक तरह) corsiKa द्वारा वर्णित इस तरह बढ़ाया जा सकता है कि सभी स्ट्रिंग्स अंत में एक बाल्टी में अकेले रखा जाता है, और उस बिंदु पर, ऐसी अकेला स्ट्रिंग के लिए एलसीपी ज्ञात है। इसके अलावा, प्रत्येक स्ट्रिंग के shustring भी जाना जाता है; यह एलसीपी की तुलना में एक लंबा है। बाल्टी सॉर्ट एक प्रत्यय सरणी के निर्माण को रोकता है लेकिन केवल आंशिक रूप से ऐसा होता है। उन तुलनाओं को निष्पादित नहीं किया गया है (जैसा कि कोरिसका द्वारा वर्णित है) वास्तव में प्रत्यय स्ट्रिंग के उन हिस्सों का प्रतिनिधित्व करते हैं जो प्रत्यय सरणी में नहीं जोड़े जाते हैं। अंत में, यह विधि न केवल एलसीपी और शटरिंग के निर्धारण के लिए अनुमति देती है, बल्कि स्ट्रिंग के भीतर मौजूद नहीं होने वाले उन अनुक्रमों को आसानी से ढूंढ सकते हैं।

Answer 7

के बाद से दुनिया जाहिर स्विफ्ट में एक जवाब के लिए भीख माँग रहा है, यहाँ मेरा है;)

func longestCommonPrefix(strings:[String]) -> String { 

    var commonPrefix = "" 
    var indices = strings.map { $0.startIndex} 

outerLoop: 

    while true { 
     var toMatch: Character = "_" 

     for (whichString, f) in strings.enumerate() { 

      let cursor = indices[whichString] 

      if cursor == f.endIndex { break outerLoop  } 

      indices[whichString] = cursor.successor() 

      if whichString == 0  { toMatch = f[cursor] } 
      if toMatch != f[cursor] { break outerLoop  } 
     } 

     commonPrefix.append(toMatch) 
    } 

    return commonPrefix 
} 

स्विफ्ट 3 अद्यतन:

func longestCommonPrefix(strings:[String]) -> String { 

    var commonPrefix = "" 
    var indices = strings.map { $0.startIndex} 

    outerLoop: 

     while true { 
      var toMatch: Character = "_" 

      for (whichString, f) in strings.enumerated() { 

       let cursor = indices[whichString] 

       if cursor == f.endIndex { break outerLoop  } 

       indices[whichString] = f.characters.index(after: cursor) 

       if whichString == 0  { toMatch = f[cursor] } 
       if toMatch != f[cursor] { break outerLoop  } 
      } 

      commonPrefix.append(toMatch) 
    } 

    return commonPrefix 
} 

दिलचस्प बात यह है गौर करने योग्य

1. यह ओ^2, या ओ (एनएक्सएम) में चलता है जहां एन स्ट्रिंग्स की संख्या है और एम सबसे छोटी की लंबाई है।
2. यह स्ट्रिंग.इंडेक्स डेटा प्रकार का उपयोग करता है और इस प्रकार Grapheme Clusters से संबंधित है जो Character प्रकार का प्रतिनिधित्व करता है।

और समारोह मैं पहली जगह में लिखने के लिए की जरूरत को देखते हुए:

/// Takes an array of Strings representing file system objects absolute 
/// paths and turn it into a new array with the minimum number of common 
/// ancestors, possibly pushing the root of the tree as many level downwards 
/// as necessary 
/// 
/// In other words, we compute the longest common prefix and remove it 

func reify(fullPaths:[String]) -> [String] { 

    let lcp = longestCommonPrefix(fullPaths) 

    return fullPaths.map { 
     return $0[lcp.endIndex ..< $0.endIndex] 
    } 
} 

यहाँ

एक न्यूनतम इकाई परीक्षण है:

func testReifySimple() { 
    let samplePaths:[String] = [ 
     "/root/some/file" 
    , "/root/some/other/file" 
    , "/root/another/file" 
    , "/root/direct.file" 
    ] 

    let expectedPaths:[String] = [ 
     "some/file" 
    , "some/other/file" 
    , "another/file" 
    , "direct.file" 
    ] 

    let reified = PathUtilities().reify(samplePaths) 

    for (index, expected) in expectedPaths.enumerate(){ 
     XCTAssert(expected == reified[index], "failed match, \(expected) != \(reified[index])") 
    } 
}