Python में एक वर्ण से भिन्न सबस्ट्रिंग्स की गिनती करने का प्रोग्राम

मान लीजिए हमारे पास दो स्ट्रिंग्स s और t हैं, हमें उन तरीकों की संख्या ढूंढनी है जिनसे हम s का एक नॉन-खाली सबस्ट्रिंग चुन सकते हैं और एक वर्ण को दूसरे अलग वर्ण से बदल सकते हैं ताकि परिणामी सबस्ट्रिंग t के सबस्ट्रिंग में से एक हो। हमें उन सबस्ट्रिंग्स की संख्या ढूंढनी है जो उपरोक्त शर्त को संतुष्ट करती हैं।

उदाहरण के लिए, यदि इनपुट है s = "sts", t = "tsts", तो आउटपुट 6 होगा क्योंकि s और t के सबस्ट्रिंग्स के निम्नलिखित जोड़े हैं जो 1 वर्ण से भिन्न हैं:

• ("sts", "tsts"),
• ("sts", "tsts"),
• ("sts", "tsts"),
• ("sts", "tsts"),
• ("sts", "tsts"),
• ("sts", "tsts")

समाधान के चरण

1. n1 := len(s)
2. n2 := len(t)
3. ans := 0
4. s से प्रत्येक इंडेक्स i1 और वर्ण c1 के लिए:
   • t से प्रत्येक इंडेक्स i2 और वर्ण c2 के लिए:
     • i := i1, j := i2
     • while i < n1 and j < n2 and s[i] == t[j]:
       • i += 1, j += 1
     • यदि i < n1 and j < n2 and s[i] != t[j]:
       • i += 1, j += 1
       • ans += 1
       • while i < n1 and j < n2 and s[i] == t[j]:
         • i += 1, j += 1
         • ans += 1
5. ans वापस करें

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें:

def solve(s, t):
    n1 = len(s)
    n2 = len(t)
    ans = 0
    for i1, c1 in enumerate(s):
        for i2, c2 in enumerate(t):
            i = i1
            j = i2
            while i < n1 and j < n2 and s[i] == t[j]:
                i += 1
                j += 1
            if i < n1 and j < n2 and s[i] != t[j]:
                i += 1
                j += 1
                ans += 1
                while i < n1 and j < n2 and s[i] == t[j]:
                    i += 1
                    j += 1
                    ans += 1
    return ans

s = "sts"
t = "tsts"
print(solve(s, t))

इनपुट

"sts", "tsts"

आउटपुट

6