Khoảng cách chỉnh sửa một (One Edit Distance) trong C++

Cho hai chuỗi s và t. Kiểm tra xem chúng có cách nhau đúng một khoảng cách chỉnh sửa hay không. Ba loại phép chỉnh sửa: chèn, xóa, hoặc thay thế một ký tự.

Ví dụ

Đầu vào: s = "ab", t = "acb"
Đầu ra: true (chèn 'c' vào s).

Thuật toán so sánh tuyến tính

1. Đảm bảo s dài hơn hoặc bằng t (hoán đổi nếu cần).
2. Duyệt đồng thời đến khi tìm thấy ký tự khác nhau tại vị trí i.
3. Nếu độ dài bằng nhau: phần còn lại sau i phải giống hệt nhau (thay thế).
4. Nếu s dài hơn: phần còn lại của s từ i+1 phải khớp với phần còn lại của t từ i (chèn vào t / xóa khỏi s).
5. Nếu duyệt hết t không thấy khác biệt: s phải dài hơn đúng 1 ký tự (chèn cuối).

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool isOneEditDistance(string s, string t) {
        if (s.size() < t.size()) return isOneEditDistance(t, s);
        int n = s.size(), m = t.size();
        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;
    }
};

Độ phức tạp

• Thời gian: O(min(N, M)) - dừng sớm khi tìm thấy khác biệt.
• Không gian: O(1) - không dùng bộ nhớ thêm (substr trong C++ có thể copy, có thể tối ưu bằng con trỏ).

Kết quả kiểm thử

Đầu vào: s = "ab", t = "acb"
Đầu ra: 1 (true)