Рубрики

Распечатать все возможные слова из цифр телефона

До появления QWERTY-клавиатур, надписи и цифры помещались на одну и ту же клавишу. Например, 2 имеет «ABC», если мы хотим написать что-нибудь, начинающееся с «A», нам нужно набрать клавишу 2 один раз. Если мы хотим набрать «B», дважды нажмите клавишу 2 и трижды введите «C». ниже изображение такой клавиатуры.

С помощью клавиатуры, показанной на рисунке, и цифрой, перечислите все возможные слова, нажав эти цифры.
Например, если введено число 234, возможные слова, которые могут быть сформированы (в алфавитном порядке):
ADG ADH ADI AEG AHE AHE AFG AFH AFI BDG BDH BDI BHE BEH BE BE BFG BFH BFI CDG CDH CDI CEG CEG CEH CEF CFF CFH CFI

Давайте сначала сделаем некоторые расчеты. Сколько слов возможно с семью цифрами, каждая из которых представляет собой n букв? Для первой цифры у нас есть максимум четыре варианта, и для каждого варианта для первой буквы у нас есть максимум четыре варианта для второй цифры и так далее. Так что это простая математика, это будет O (4 n ). Поскольку клавиши 0 и 1 не имеют соответствующего алфавита, а многие символы имеют 3 символа, 4 n будет верхней границей количества слов, а не минимальных слов.

Теперь давайте сделаем несколько примеров.
Для числа выше 234. Видите ли вы какой-либо шаблон? Да, мы замечаем, что последний символ всегда либо G, H, либо I, и когда он сбрасывает свое значение с I на G, цифра слева от него изменяется.
Точно так же всякий раз, когда второй последний алфавит сбрасывает свое значение, третий последний алфавит получает изменения и так далее. Первый символ сбрасывается только один раз, когда мы сгенерировали все слова. Это можно посмотреть и с другого конца. То есть всякий раз, когда символ в позиции i изменяется, персонаж в позиции i + 1 проходит через все возможные символы и создает волновой эффект, пока мы не достигнем конца.
Так как 0 и 1 не имеют никаких символов, связанных с ними. мы должны сломаться, так как не будет итерации для этих цифр.
Давайте возьмем второй подход, так как его будет легко реализовать с помощью рекурсии. Идем до конца и возвращаемся один за другим. Идеальное состояние для рекурсии. давайте искать базовый случай.
Когда мы достигаем последнего символа, мы печатаем слово со всеми возможными символами для последней цифры и возвращаем. Простой базовый вариант.
Когда мы достигаем последнего символа, мы печатаем слово со всеми возможными символами для последней цифры и возвращаем. Простой базовый вариант.

Ниже приведена реализация рекурсивного подхода для печати всех возможных слов, соответствующих вводимому цифре. Обратите внимание, что входной номер представлен в виде массива для упрощения кода.

С

#include <stdio.h>
#include <string.h>

  
// hashTable [i] хранит все символы, которые соответствуют цифре i в телефоне

const char hashTable[10][5] = {"", "", "abc", "def", "ghi", "jkl",

                               "mno", "pqrs", "tuv", "wxyz"};

  
// Рекурсивная функция для печати всех возможных слов, которые можно получить
// по входному номеру [] размера n. Выходные слова хранятся одно за другим
// в выводе []

void  printWordsUtil(int number[], int curr_digit, char output[], int n)

{

    // Базовый случай, если подготовлено текущее выходное слово

    int i;

    if (curr_digit == n)

    {

        printf("%s ", output);

        return ;

    }

  

    // Попробуйте все 3 возможных символа для текущего дигира в числе []

    // и повторить оставшиеся цифры

    for (i=0; i<strlen(hashTable[number[curr_digit]]); i++)

    {

        output[curr_digit] = hashTable[number[curr_digit]][i];

        printWordsUtil(number, curr_digit+1, output, n);

        if (number[curr_digit] == 0 || number[curr_digit] == 1)

            return;

    }

}

  
// Оболочка над printWordsUtil (). Создает выходной массив и
// вызывает printWordsUtil ()

void printWords(int number[], int n)

{

    char result[n+1];

    result[n] ='\0';

    printWordsUtil(number, 0, result, n);

}

  
// Драйвер программы

int main(void)

{

    int number[] = {2, 3, 4};

    int n = sizeof(number)/sizeof(number[0]);

    printWords(number, n);

    return 0;

}

python3

# hashTable [i] хранит все символы
# соответствует цифре i в телефоне

hashTable = ["", "", "abc", "def", "ghi", "jkl", 

                    "mno", "pqrs", "tuv", "wxyz"]

  
# Рекурсивная функция для печати всех
# возможные слова, которые можно получить
# по номеру ввода [] размера n.
# выходные слова хранятся одно за другим
# в выводе []

def printWordsUtil(number, curr, output, n):

    if(curr == n):

        print(output)

        return

          

    # Попробуйте все 3 возможных символа

    # для текущего дигира в номере []

    # и повторить оставшиеся цифры

    for i in range(len(hashTable[number[curr]])):

        output.append(hashTable[number[curr]][i])

        printWordsUtil(number, curr + 1, output, n)

        output.pop()

        if(number[curr] == 0 or number[curr] == 1):

            return

              
# Оболочка над printWordsUtil ().
# Создает выходной массив и
# вызывает printWordsUtil ()

def printWords(number, n):

    printWordsUtil(number, 0, [], n)

      
# Функция драйвера

if __name__ == '__main__':

    number = [2, 3, 4]

    n = len(number)

    printWords(number, n);

      
# Этот код предоставлен prajmsidc


Выход:

adg adh adi aeg aeh aei afg afh afi bdg 
bdh bdi beg beh bei bfg bfh bfi cdg cdh 
cdi ceg ceh cei cfg cfh cfi
Process returned 0 (0x0)   execution time : 0.025 s
Press any key to continue.

Сложность времени: временная сложность вышеприведенного кода составляет O (4 n ), где n — количество цифр во входном номере.

Ссылка:
Купить интервью для программистов: секреты получения вашей следующей работы 3-е издание от Flipkart.com

Эта статья предоставлена Джитендрой Сангар . Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Распечатать все возможные слова из цифр телефона

0.00 (0%) 0 votes