In Tất Cả Chuỗi Xen Kẽ Của Hai Chuỗi Cho Trước Trong C++

Trong bài toán này, chúng ta được cho hai chuỗi str1 và str2 và phải in tất cả các chuỗi xen kẽ (interleaving) từ cả hai chuỗi.

Chuỗi xen kẽ được tạo từ hai chuỗi cho trước sao cho thứ tự ký tự của mỗi chuỗi được giữ nguyên.

Ví dụ để hiểu vấn đề:

Đầu vào: str1 = "XY", str2 = "NS"
Đầu ra: XYNS, XNYS, XNSY, NXYS, NXSY, NSXY

Để giải quyết, ta lấy tất cả ký tự trong hai chuỗi. Độ dài str1 = m, str2 = n, ta sinh tất cả chuỗi xen kẽ từ chúng.

Để in tất cả chuỗi xen kẽ, ta cố định ký tự của các chuỗi và gọi đệ quy cho tất cả tổ hợp của chuỗi.

Ví Dụ

Triển khai logic:

#include <iostream>
#include <string.h>
using namespace std;

void printStrings(char *str1, char *str2, char *iStr, int m, int n, int i) {
    if (m == 0 && n == 0)
        cout << iStr << endl;
    if (m != 0) {
        iStr[i] = str1[0];
        printStrings(str1 + 1, str2, iStr, m - 1, n, i + 1);
    }
    if (n != 0) {
        iStr[i] = str2[0];
        printStrings(str1, str2 + 1, iStr, m, n - 1, i + 1);
    }
}

void generateInterleavingString(char *str1, char *str2, int m, int n) {
    char *iStr = new char[((m + n + 1) * sizeof(char))];
    iStr[m + n] = '\0';
    printStrings(str1, str2, iStr, m, n, 0);
}

int main() {
    char str1[] = "XY";
    char str2[] = "NS";
    cout << "Tất cả chuỗi xen kẽ là:\n";
    generateInterleavingString(str1, str2, strlen(str1), strlen(str2));
    return 0;
}

Đầu Ra

Tất cả chuỗi xen kẽ là: XYNS XNYS XNSY NXYS NXSY NSXY