Một khoảng cách chỉnh sửa trong C ++

Giả sử chúng ta có hai chuỗi s và t; chúng ta phải kiểm tra xem chúng có cách nhau một khoảng cách chỉnh sửa hay không. Khoảng cách chỉnh sửa một lần có ba loại -

• Chèn một ký tự vào s để nhận được t

• Xóa một ký tự khỏi s để lấy t

• Thay thế một ký tự của s để nhận được t

Vì vậy, nếu đầu vào là s =​​"ab", t ="acb", thì đầu ra sẽ là True

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• n:=kích thước của s, m:=kích thước của t

• nếu n

  • return isOneEditDistance (t, s)

• để khởi tạo i:=0, khi i

  • nếu s [i] không bằng t [i] thì -

    • nếu n giống với m thì -

      • trả về true khi chuỗi con của s từ chỉ mục 0 đến (i) giống với chuỗi con của t từ chỉ mục 0 đến (i)

    • trả về true khi chuỗi con của s từ chỉ mục 0 đến (i) giống với chuỗi con của t từ chỉ mục 0 đến (i - 1)

• trả về true khi m + 1 giống với n

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơ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"));
}

Đầu vào

s = "ab", t = "acb"

Đầu ra

1