Đếm chuỗi trở thành một trong hai chuỗi cho trước sau khi xóa một ký tự trong C++

Cho hai chuỗi khác nhau s1 và s2. Nhiệm vụ: tạo chuỗi S bằng cách kết hợp các ký tự duy nhất của s1 và s2, sau đó kiểm tra nếu xóa một ký tự khỏi S có tạo được chuỗi bằng s1 HOẶC s2 hay không.

Ví dụ

Đầu vào: S1 = "utter", S2 = "butter"

Đầu ra: Số chuỗi thỏa mãn: 1

Giải thích: Chuỗi S = "butter". Xóa 'b' → "utter" = s1 → đếm = 1.

Đầu vào: S1 = "fat", S2 = "rat"

Đầu ra: Số chuỗi thỏa mãn: 2

Giải thích: Chuỗi S = "frat". Xóa 'r' → "fat" = s1. Xóa 'f' → "rat" = s2 → đếm = 2.

Phương pháp sử dụng

• Khai báo hai chuỗi s1, s2 và tính độ dài s1 truyền cho hàm.
• Khởi tạo count = 2 (kết quả tối đa là 2).
• Tìm chỉ số start đầu tiên mà s1[i] != s2[i].
• Tìm chỉ số end cuối cùng mà s1[i] != s2[i].
• Nếu end < start: count = 26 * (size_S1 + 1) trả về.
• Nếu start == end trả về count.
• Ngược lại: duyệt từ start+1 đến end, nếu s1[i] != s2[i-1] giảm count.
• Duyệt từ start+1 đến end, nếu s1[i-1] != s2[i] giảm count.
• Trả về count.

Ví dụ mã nguồn

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

int equal_removal(string S1, string S2, int size_S1) { 
    int count = 2; 
    int start, end; 
    for (int i = 0; i < size_S1; ++i) { 
        if (S1[i] != S2[i]) { 
            start = i; 
            break; 
        } 
    } 
    for (int i = size_S1 - 1; i >= 0; i--) { 
        if (S1[i] != S2[i]) { 
            end = i; 
            break; 
        } 
    } 
    if (end < start) { 
        count = 26 * (size_S1 + 1); 
        return count; 
    } else if (start == end) { 
        return count; 
    } else { 
        for (int i = start + 1; i <= end; i++) { 
            if (S1[i] != S2[i - 1]) { 
                count--; 
                break; 
            } 
        } 
        for (int i = start + 1; i <= end; i++) { 
            if (S1[i - 1] != S2[i]) { 
                count--; 
                break; 
            } 
        } 
        return count; 
    } 
} 

int main() { 
    string S1 = "utter"; 
    string S2 = "butter"; 
    int size_S1 = S1.length(); 
    cout << "Count of strings that become equal to one of the two strings after one removal are: " << equal_removal(S1, S2, size_S1); 
    return 0; 
}

Chạy mã trên cho kết quả:

Kết quả

Count of strings that become equal to one of the two strings after one removal are: 1