พิมพ์คำทั้งหมดที่เป็นไปได้จากตัวเลขโทรศัพท์ใน C++

ในปัญหานี้ เราจะได้รับตัวเลข และต้องพิมพ์คำทั้งหมดที่สามารถสร้างได้จากการกดปุ่มตัวเลขเหล่านั้นบนแป้นพิมพ์โทรศัพท์มือถือรุ่นเก่า

เราคุ้นเคยดีกับแป้นพิมพ์แบบ QWERTY ที่ใช้อยู่ในปัจจุบัน แต่ก่อนที่จะมีแป้นพิมพ์ QWERTY โทรศัพท์มือถือจะมีแป้นพิมพ์ 12 ปุ่ม ซึ่งแต่ละปุ่มจะมีทั้งตัวเลขและตัวอักษร ตัวอย่างเช่น ปุ่มหมายเลข 6 จะมีตัวอักษร "MNO" ซึ่งจะพิมพ์ได้โดยการกดปุ่ม 1 ครั้ง 2 ครั้ง หรือ 3 ครั้ง

รูปแบบแป้นพิมพ์จะเป็นดังนี้:

ในแป้นพิมพ์เหล่านี้ ตัวอักษรทั้งหมดก็จะมีอยู่ และผู้ใช้สามารถพิมพ์ได้ ดังนั้นในปัญหานี้ เราจะพิมพ์คำทั้งหมดที่เป็นไปได้ที่สามารถสร้างได้จากลำดับตัวเลขที่กำหนด

ตัวอย่างเพื่อความเข้าใจ

Input: 687
Output: MTP, MTQ, MTR, MTS, MUP, MUQ, MUR, MUS, MVP, MVQ, MVR, MVS, NTP, NTQ, NTR, NTS, NUP, NUQ, NUR, NUS, NVP, NVQ, NVR, NVS, OTP, OTQ, OTR, OTS, OUP, OUQ, OUR, OUS, OVP, OVQ, OVR, OVS

เพื่อแก้ปัญหานี้ ให้ดูรูปแบบที่เกิดขึ้นในตัวอย่างข้างต้น แต่ละปุ่มมีตัวอักษรที่เกี่ยวข้องของตัวเอง และเราจะต้องใช้ตัวอักษรเหล่านั้นขณะพิมพ์ ดังนั้นสำหรับแต่ละตัวเลข จะมีตัวเลือกสูงสุด 4 ตัวเลือก (ในกรณีของ 7 และ 9) สำหรับเรื่องนี้ เราสามารถกำหนดตัวเลขหนึ่งตัว แล้วใช้ตัวเลขถัดไปเพื่อสร้างคำ ซึ่งสามารถทำได้โดยใช้การเรียกซ้ำ (recursion)

โปรแกรมตัวอย่าง

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

const char keypad[10][5] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

void printWords(int number[], int curr_digit, char output[], int n) {
    int i;
    if (curr_digit == n) {
        cout << output << " ";
        return;
    }
    for (i = 0; i < strlen(keypad[number[curr_digit]]); i++) {
        output[curr_digit] = keypad[number[curr_digit]][i];
        printWords(number, curr_digit + 1, output, n);
        if (number[curr_digit] == 0 || number[curr_digit] == 1)
            return;
    }
}

int main(void) {
    int number[] = {6, 8, 7};
    cout << "The output character formed is : \n";
    int n = sizeof(number) / sizeof(number[0]);
    char result[n + 1];
    result[n] = '\0';
    printWords(number, 0, result, n);
    return 0;
}

ผลลัพธ์

ตัวอักษรที่สร้างขึ้นคือ:

mtp mtq mtr mts mup muq mur mus mvp mvq mvr mvs ntp ntq ntr nts nup nuq nur nus nvp nvq nvr nvs otp otq otr ots oup ouq our ous ovp ovq ovr ovs