মান ল করুন S এবং T নামের দুটি স্ট্রিং, আমাদের যাচাই করতে হবে তারা এক বা শূন্য এডিট ডিস্ট্যান্সে আছে কিনা। এডিট অপারেশন হল: একটি ক্যারেক্টার ডিলিট করা, একটি ক্যারেক্টার যোগ করা, বা একটি ক্যারেক্টারকে অন্য ক্যারেক্টারের সাথে রিপ্লেস করা।
যদি ইনপুট হয় S = "hello", T = "hallo", তবে আউটপুট হবে True, কারণ এই দুটি স্ট্রিংয়ের এডিট ডিস্ট্যান্স ১।
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব:
- m := S-এর আকার, n := T-এর আকার
- i := 0, j := 0, count := 0
- যদি |m - n| > 1 হয়, তবে False ফেরত দিন
- যখন i < m এবং j < n:
- যদি S[i] != T[j] হয়:
- যদি count == 1, False ফেরত দিন
- যদি m < n, j := j + 1
- অন্যথায় যদি m > n, i := i + 1
- অন্যথায়, i := i + 1, j := j + 1
- count := count + 1
- অন্যথায়, i := i + 1, j := j + 1
- যদি S[i] != T[j] হয়:
- True ফেরত দিন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:
উদাহরণ
class Solution: def solve(self, S, T): m, n = len(S), len(T) i, j = 0, 0 count = 0 if abs(m - n) > 1: return False while i < m and j < n: if S[i] != T[j]: if count == 1: return False if m < n: j += 1 elif m > n: i += 1 else: i += 1 j += 1 count += 1 else: i += 1 j += 1 return True ob = Solution() S = "hello" T = "hallo" print(ob.solve(S, T))
ইনপুট
"hello", "hallo"
আউটপুট
True
