11

Possible combinations of characters on the telephone number of a telephone

 3 years ago
source link: https://www.codesd.com/item/possible-combinations-of-characters-on-the-telephone-number-of-a-telephone.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Possible combinations of characters on the telephone number of a telephone

advertisements

I was faced with a question recently in C. We have a phone's numpad with following layout:

1[abc] 2[def] 3[ghi]
4[jkl] 5[mno] 6[pqr]
7[st]  8[uv]  9[wx]
       0[yz]

How to come up with an API which gives all possible combinations of characters belonging to each number for a given numeral input. For e.g. input = 1234

Then the API should print all possible combinations of characters-

adgj bdgj cdgj aegj begj cegj.. and so on.

Is there a simple way to do it? Apart from hardcoded nested for loops. I was given a hint as recursion but couldn't figure a way out of it.

Recursion is a good solution for such problems, where you must find combinations. The advantage over nested loops is that recursion works for strings of any length.

In your case, you need a function that takes:

  • the original string
  • an auxiliary char buffer for the solution* and
  • the current index, which starts at 0.

Recursive functions require a termination condition: When you have reached the end of the original string, print it and return.

Otherwise, take the next digit, check whether it is valid, determine the letters associated with it and then call the function for each of the letters. That is, for each letter, copy it to the solution at the current index, then call the function with the next index.

Below's an example implementation that uses an intermediate function to do some house-keeping:

#include <stdlib.h>
#include <stdio.h>

/*
 *      Recursive back-end, that produces all combinations in sol.
 */
void alpha_r(const char *str, char *sol, int index)
{
    const char *combo[] = {
        "yz", "abc", "def", "ghi", "jkl", "mno", "pqr", "st", "uv", "wx"
    };

    if (str[index] == '\0') {
        printf("%s\n", sol);
    } else {
        int k = str[index] - '0';
        const char *p = combo[k];

        while (*p) {
            sol[index] = *p++;
            alpha_r(str, sol, index + 1);
        }
    }
}

/*
 *      Non-recursive front-end that checks the string for validity
 *      and creates a temporary buffer for the solutions.
 */
void alpha(const char *str)
{
    int len = 0;

    while (str[len]) {
        if (str[len] < 0 || str[len] > '9') {
            fprintf(stderr, "Invalid input.\n");
            return;
        }
        len++;
    }

    char sol[len + 1];

    sol[len] = '\0';
    alpha_r(str, sol, 0);
}

int main()
{
    alpha("123");

    return 0;
}

*) You could also use the string itself to store the solutions.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK