পাইথনে এক ক্যারেক্টার দিয়ে ডিফারেন্স করে সাবস্ট্রিং মিলানোর প্রোগ্রাম

মান লিজিয়ে দুটি স্ট্রিং আছে s এবং t, আমাদের বের করতে হবে কতভাবে আমরা s-এর একটি নন-ইম্পটি সাবস্ট্রিং বাছাই করে সেটির এক একক ক্যারেক্টার পরিবর্তন করে t-এর একটি সাবস্ট্রিং তৈরি করতে পারি। যেসব সাবস্ট্রিং এই শর্ত পূরণ করে তাদের সংখ্যা বের করতে হবে।

যেমন, ইনপুট হলে s = "sts", t = "tsts", তবে আউটপুট হবে 6 কারণ নিচের জোড়াগুলো এক ক্যারেক্টারের পার্থক্যে মেলে: ("sts", "tsts") (৬টি ভিন্ন পজিশন কম্বিনেশন)।

সমাধানের ধাপসমূহ

• n1 := len(s), n2 := len(t)

• ans := 0

• s-এ প্রতিটি (i1, c1) এর জন্য:

  • t-এ প্রতিটি (i2, c2) এর জন্য:

    • i := i1, j := i2

    • 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

      • i < n1 and j < n2 and s[i] == t[j] থাকা পর্যন্ত: i += 1, j += 1, ans += 1

• 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