Kiểm tra chuỗi rỗng bằng cách xóa đệ quy chuỗi con trong C++

Cho 2 chuỗi str1 và str2 (str2 là chuỗi con của str1). Lặp lại việc xóa **mọi lần xuất hiện** của str2 trong str1. Kiểm tra str1 có trở thành chuỗi rỗng hay không.

Ví dụ

Đầu vào: str1 = "CCCPPPPPP", str2 = "CPP"

Quá trình:

1. "CCCPPPPPP" -> xóa "CPP" (tại vị trí 2) -> "CCPPPP"
2. "CCPPPP" -> xóa "CPP" (tại vị trí 1) -> "CPP"
3. "CPP" -> xóa "CPP" -> "" (Rỗng)

Đầu ra: True

Phương pháp giải

Sử dụng hàm string::find để tìm vị trí, string::erase để xóa. Lặp cho đến khi không tìm thấy hoặc chuỗi rỗng.

Lưu ý hiệu năng: erase trong `std::string` có độ phức tạp O(N) do dịch chuyển bộ nhớ. Với chuỗi rất dài, cách này chậm (O(N²)). Có thể tối ưu bằng **Stack** hoặc **KMP** để xử lý tuyến tính, nhưng code dưới đây minh họa logic đúng theo đề bài.

Chương trình C++ (Đơn giản, đúng logic)

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

bool canBecomeEmpty(string str1, const string& str2) {
    if (str2.empty()) return str1.empty(); // Tránh vòng lặp vô tận
    
    size_t pos;
    while ((pos = str1.find(str2)) != string::npos) {
        str1.erase(pos, str2.length());
    }
    return str1.empty();
}

int main() {
    string s1 = "CCCPPPPPP", s2 = "CPP";
    cout << "str1: " << s1 << ", str2: " << s2 << " -> " 
         << (canBecomeEmpty(s1, s2) ? "True" : "False") << endl;

    // Test case khác
    cout << "GCCGCC, GCC -> " << (canBecomeEmpty("GCCGCC", "GCC") ? "True" : "False") << endl; // True
    cout << "ABCABC, ABC -> " << (canBecomeEmpty("ABCABC", "ABC") ? "True" : "False") << endl; // True
    cout << "AAAA, AA -> " << (canBecomeEmpty("AAAA", "AA") ? "True" : "False") << endl; // True
    cout << "ABCD, AB -> " << (canBecomeEmpty("ABCD", "AB") ? "True" : "False") << endl; // False (con "CD")
    return 0;
}

Đầu ra

str1: CCCPPPPPP, str2: CPP -> True
GCCGCC, GCC -> True
ABCABC, ABC -> True
AAAA, AA -> True
ABCD, AB -> False