Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

पायथन में दो दी गई स्ट्रिंग्स के कॉमन स्पेशल सबस्ट्रिंग्स का आकार ढूंढना


मान लीजिए हमारे पास दो स्ट्रिंग्स s1 और s2 हैं। हमें सबसे लंबी स्ट्रिंग s3 का आकार ढूंढना है जो s1 और s2 दोनों का स्पेशल सबस्ट्रिंग है।

हम कह सकते हैं कि एक स्ट्रिंग x दूसरी स्ट्रिंग y का स्पेशल सबस्ट्रिंग है यदि x को y से 0 या अधिक अक्षर हटाकर उत्पन्न किया जा सकता है।

उदाहरण के लिए, यदि इनपुट है s1 = 'pineapple', s2 = 'people', तो आउटपुट होगा 5 क्योंकि स्पेशल सबस्ट्रिंग 'peple' है, जिसका आकार 5 है।

समाधान दृष्टिकोण

यह क्लासिक लॉन्गेस्ट कॉमन सबसीक्वेंस (LCS) समस्या है जिसे O(n*m) समय में डायनामिक प्रोग्रामिंग का उपयोग करके हल किया जाता है। यहां स्पेस-अनुकूलित संस्करण दो पंक्तियों (prev और cur) का उपयोग करता है।

  • prev को डिफ़ॉल्ट 0 वाले डिक्शनरी के रूप में आरंभ करें।
  • s1 के प्रत्येक अक्षर i के लिए:
    • नई cur डिक्शनरी बनाएं।
    • s2 के प्रत्येक अक्षर j के लिए:
      • यदि s1[i] == s2[j], तो cur[j] = prev[j-1] + 1।
      • अन्यथा cur[j] = max(cur[j-1], prev[j])।
    • prev = cur सेट करें।
  • prev[len(s2)-1] लौटाएं।

पायथन कार्यान्वयन

from collections import defaultdict

def solve(s1, s2):
    prev = defaultdict(int)
    for i in range(len(s1)):
        cur = defaultdict(int)
        for j in range(len(s2)):
            cur[j] = prev[j - 1] + 1 if s1[i] == s2[j] else max(cur[j - 1], prev[j])
        prev = cur
    return prev[len(s2)-1]

s1 = 'pineapple'
s2 = 'people'
print(solve(s1, s2))

इनपुट

'pineapple', 'people'

आउटपुट

5

  1. पायथन में दिए गए ग्राफ में विशेष प्रकार के उपग्राफ ज्ञात करने का प्रोग्राम पायथन में दिए गए ग्राफ में विशेष प्रकार के उपग्राफ ज्ञात करने का प्रोग्राम

    मान लीजिए हमारे पास एक विशेष प्रकार का ग्राफ है जिसमें दो प्रकार के शीर्ष हैं जिन्हें हेड और फीट कहा जाता है। ग्राफ में केवल एक हेड होता है और k किनारे होते हैं जो हेड को प्रत्येक फीट से जोड़ते हैं। इसलिए, यदि हमें एक अनिर्देशित, अनभारित ग्राफ दिया जाता है; तो हमें ग्राफ के शीर्ष-असंयुक्त उपग्राफ म

  1. - Python प्रोग्राम से जांचें कि कोई संख्या दो की घात है या नहीं

    इस लेख में, हम नीचे दिए गए समस्या कथन के समाधान के बारे में जानेंगे। समस्या कथन - हमें एक संख्या दी गई है, हमें जांचने की आवश्यकता है कि संख्या दो की घात है या नहीं। हम इसे नीचे चर्चा किए गए दो दृष्टिकोणों का उपयोग करके हल कर सकते हैं। दृष्टिकोण 1: दिए गए संख्या का बेस 2 पर लॉग लेकर घात प्राप्त क

  1. पायथन प्रोग्राम: दो स्ट्रिंग्स से असामान्य शब्द खोजें पायथन प्रोग्राम: दो स्ट्रिंग्स से असामान्य शब्द खोजें

    इस लेख में हम दी गई समस्या के समाधान के बारे में जानेंगे। समस्या कथन हमें दो स्ट्रिंग्स दी गई हैं, हमें दी गई स्ट्रिंग्स से असामान्य शब्द प्राप्त करने हैं। उदाहरण # असामान्य शब्द def find(A, B): # काउंट count = {} # A में डालें for word in A.split(): count[word] = count.get(w