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

สมมติว่าเรามีสตริงสองสตริง s และ t เราต้องตรวจสอบว่าทั้งสองอยู่ห่างกันเพียงหนึ่งการแก้ไข (one edit distance) การแก้ไขหนึ่งครั้งมี 3 ประเภท:

• แทรกตัวอักษรเข้า s เพื่อได้ t
• ลบตัวอักษรจาก s เพื่อได้ t
• แทนที่ตัวอักษรใน s เพื่อได้ t

ตัวอย่าง: s = "ab", t = "acb" ผลลัพธ์ = true

วิธีแก้ปัญหา

1. ให้ n = |s|, m = |t| ถ้า n < m สลับ s และ t
2. หาตำแหน่งแรกที่ตัวอักษรต่างกัน
3. ถ้าความยาวเท่ากัน: ตรวจสอบ substring หลังตำแหน่งนั้น
4. ถ้าความยาวต่างกัน: ตรวจสอบ substring ของ s ตัดตัวที่ต่างออก vs t
5. ถ้าไม่เจอความต่าง: ต้องมี n = m + 1

ตัวอย่างโค้ด C++

#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; 
    } 
}; 

int main(){ 
    Solution ob; 
    cout << (ob.isOneEditDistance("ab", "acb")); 
}

ข้อมูลนำเข้า

s = "ab", t = "acb"

ผลลัพธ์

1