पायथन में जांचें कि दो स्ट्रिंग्स के बीच संपादन दूरी एक है या नहीं

मान लीजिए हमारे पास दो स्ट्रिंग्स s और t हैं। हमें जांचना है कि s और t के बीच संपादन दूरी ठीक एक है या नहीं। यहां दो स्ट्रिंग्स के बीच संपादन का अर्थ इन तीन में से कोई भी है:

• एक वर्ण डालें
• एक वर्ण हटाएं
• एक वर्ण बदलें

इसलिए, यदि इनपुट s = "hello", t = "heillo" है, तो आउटपुट True होगा क्योंकि हमें s में एक वर्ण डालकर t प्राप्त करने की आवश्यकता है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:

• यदि |s का आकार - t का आकार| > 1, तो
  • false लौटाएं
• edit_dist_cnt := 0, i := 0, j := 0
• जब i < s का आकार और j < t का आकार हो, तब तक करें
  • यदि s[i], t[j] के समान नहीं है, तो
    • यदि edit_dist_cnt 1 के समान है, तो
      • false लौटाएं
    • यदि s का आकार > t का आकार, तो
      • i := i + 1
    • अन्यथा जब s का आकार < t का आकार, तो
      • j := j + 1
    • अन्यथा,
      • i := i + 1, j := j + 1
    • edit_dist_cnt := edit_dist_cnt + 1
  • अन्यथा,
    • i := i + 1, j := j + 1
• यदि i < s का आकार या j < t का आकार, तो
  • edit_dist_cnt := edit_dist_cnt + 1
• True लौटाएं जब edit_dist_cnt 1 के समान हो, अन्यथा 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