In tất cả các từ có thể từ các chữ số điện thoại trong C++

Trong bài toán này, chúng ta được cho một số và phải in ra tất cả các từ có thể tạo thành bằng cách nhấn các phím đó trên bàn phím di động kiểu cũ.

Chúng ta khá quen thuộc với kiểu bàn phím QWERTY ngày nay. Nhưng trước khi bàn phím QWERTY ra đời, các điện thoại được trang bị bàn phím 12 phím, mỗi phím chứa cả chữ cái và số. Ví dụ phím số 6 sẽ chứa các chữ cái "MNO" được gõ bằng cách nhấn 1, 2 hoặc 3 lần.

Bàn phím trông như sau:

Trên bàn phím này cũng có tất cả các chữ cái và người dùng có thể gõ chúng. Vì vậy, trong bài toán này, chúng ta sẽ in ra tất cả các từ có thể tạo thành từ dãy số cho trước.

Hãy lấy một ví dụ để hiểu rõ hơn:

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

Để giải bài toán này, hãy xem xét quy luật trong ví dụ trên. Mỗi phím có tập ký tự riêng và chúng ta phải sử dụng chúng khi gõ. Với mỗi số, có tối đa 4 lựa chọn (trường hợp phím 7 và 9). Ta có thể cố định một chữ số và sau đó dùng đệ quy để sinh từ.

Chương trình minh họa

#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 << "Các ký tự tạo thành là: \n";
    int n = sizeof(number) / sizeof(number[0]);
    char result[n + 1];
    result[n] = '\0';
    printWords(number, 0, result, n);
    return 0;
}

Kết quả

Các ký tự tạo thành là:

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