ধরি আমাদের দুটি স্ট্রিং s এবং t আছে। আমাদের যাচাই করতে হবে s এবং t-এর এডিট ডিস্ট্যান্স ঠিক এক কিনা। এডিট ডিস্ট্যান্স বলতে বুঝায়:
- একটি ক্যারেক্টার ইনসার্ট করা
- একটি ক্যারেক্টার ডিলিট করা
- একটি ক্যারেক্টার রিপ্লেস করা
উদাহরণস্বরূপ, s = "hello" এবং t = "heillo" হলে আউটপুট হবে True, কারণ s-এ একটি ক্যারেক্টার ইনসার্ট করলে t হয়।
সমাধানের ধাপসমূহ
- যদি |len(s) - len(t)| > 1, তবে false রিটার্ন করুন
- edit_dist_cnt := 0, i := 0, j := 0
- যতক্ষণ i < len(s) এবং j < len(t):
- যদি s[i] != t[j]:
- যদি edit_dist_cnt == 1, তবে false রিটার্ন করুন
- যদি len(s) > len(t), তবে i বাড়ান
- যদি len(s) < len(t), তবে j বাড়ান
- অন্যথায় i, j উভয় বাড়ান
- edit_dist_cnt বাড়ান
- অন্যথায় i, j উভয় বাড়ান
- যদি s[i] != t[j]:
- যদি i < len(s) বা j < len(t), তবে edit_dist_cnt বাড়ান
- edit_dist_cnt == 1 হলে true, অন্যথায় false রিটার্ন করুন
উদাহরণ
def solve(s, t):
if abs(len(s) - len(t)) > 1:
return False
edit_dist_cnt = 0
i = 0
j = 0
while i < len(s) and j < len(t):
if s[i] != t[j]:
if edit_dist_cnt == 1:
return False
if len(s) > len(t):
i += 1
elif len(s) < len(t):
j += 1
else:
i += 1
j += 1
edit_dist_cnt += 1
else:
i += 1
j += 1
if i < len(s) or j < len(t):
edit_dist_cnt += 1
return edit_dist_cnt == 1
s = "hello"
t = "heillo"
print(solve(s, t))
ইনপুট
"hello", "heillo"
আউটপুট
True
