หนึ่งแก้ไขระยะทางใน C++

สมมติว่าเรามีสองสตริง s และ t; เราต้องตรวจสอบว่าทั้งสองระยะการแก้ไขห่างกันหรือไม่ ระยะแก้ไขหนึ่งมีสามประเภท -

• ใส่อักขระลงใน s เพื่อรับ t

• ลบอักขระจาก s เพื่อรับ t

• แทนที่อักขระของ s เพื่อรับ t

ดังนั้น หากอินพุตเป็น s ="ab", t ="acb" ผลลัพธ์จะเป็น True

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• n :=ขนาดของ s, m :=ขนาดของ t

• ถ้า n

  • ส่งคืน isOneEditDistance(t, s)

• สำหรับการเริ่มต้น i :=0 เมื่อ i

  • ถ้า s[i] ไม่เท่ากับ t[i] แล้ว −

    • ถ้า n เท่ากับ m แล้ว −

      • คืนค่า จริง เมื่อสตริงย่อยของ s จากดัชนี 0 ถึง (i) เหมือนกับสตริงย่อยของ t จากดัชนี 0 ถึง (i)

    • คืนค่า จริง เมื่อสตริงย่อยของ s จากดัชนี 0 ถึง (i) เหมือนกับสตริงย่อยของ t จากดัชนี 0 ถึง (i - 1)

• คืนค่า จริง เมื่อ m + 1 เท่ากับ n

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool isOneEditDistance(string s, string t) {
      int n = s.size();
      int m = t.size();
      if (n < m) {
         return isOneEditDistance(t, s);
      }
      for (int i = 0; i < m; i++) {
         if (s[i] != t[i]) {
            if (n == m) {
               return s.substr(i + 1) == t.substr(i + 1);
            }
            return s.substr(i + 1) == t.substr(i);
         }
      }
      return m + 1 == n;
   }
};
main(){
   Solution ob;
   cout << (ob.isOneEditDistance("ab", "acb"));
}

อินพุต

s = "ab", t = "acb"

ผลลัพธ์

1