พิมพ์ Interleaving Strings ทั้งหมดของสองสตริงใน C++

ภาพรวมปัญหา

ได้รับสตริง str1 และ str2 ต้องพิมพ์ Interleaving Strings ทั้งหมด (สตริงที่สร้างจากการผสมสองสตริงโดยรักษาลำดับตัวอักษรของแต่ละสตริง)

ตัวอย่าง

Input: str1 = "XY", str2 = "NS"
Output: XYNS, XNYS, XNSY, NXYS, NXSY, NSXY

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

1. สร้างบัฟเฟอร์ขนาด m+n
2. แต่ละขั้นตอนเลือกตัวอักษรจาก str1 หรือ str2
3. เรียกซ้ำจนทั้งสองสตริงหมด

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

#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 << "All interleaving strings are:\n";
    generateInterleavingString(str1, str2, strlen(str1), strlen(str2));
    return 0;
}

ผลลัพธ์ (Output)

All interleaving strings are:
XYNS XNYS XNSY NXYS NXSY NSXY