Комбінації літер телефонного номера  


Рівень складності Medium
Часто запитують у Амазонка Apple Atlassian Capital One Збір даних eBay Facebook Google Microsoft Morgan Stanley оракул Qualtrics Twilio Убер VMware Лабораторії Walmart
Зворотний трек Глибина Перший пошук Рекурсія рядок

У комбінаціях літер проблеми телефонного номера ми дали a рядок що містять цифри від 2 до 9. Проблема полягає в тому, щоб знайти всі можливі комбінації, які могли б бути представлені цим числом, якщо кожному номеру присвоєно кілька букв. Присвоєння номера наведено нижче, як і кнопки телефону.

Комбінації літер телефонного номераPin

Зверніть увагу, що тут жодна буква не присвоєна

Приклад  

"23"
["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]

Букви, присвоєні "2" він має "ABC" і "3" він має "DEF" тому поєднання букв буде "ad", "ae", "af", "bd", "be", "bf", "cd", "ce" і "cf"

Алгоритм  

  1. Заявіть a Чергу і ArrayList і рядок масив.
  2. Рядковий масив повинен зберігати значення, як задано рядок keyWords [10] = {“”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “ wxyz "};
  3. Спочатку вставте порожній рядок у чергу
  4. Хоча в черзі є деякі значення, вона перебирається по циклу.
  5. Збережіть значення фронту черги у тимчасовий рядок
  6. Якщо довжина тимчасового рядка виявиться рівною n (що є довжиною вхідного значення), тоді
  7. Додайте значення тимчасового рядка до списку.
  8. В іншому випадку відкрийте цикл, в якому значення рядка ініціалізується як копія = ключі [номер [temp.length ()]];
  9. Додайте тимчасовий рядок до підрядка кожного ключового слова (0, 1) і вставте його в чергу.
  10. Взаємодіє над ним, доки в черзі не буде значень.
  11. Список повернення.
Дивись також
Діти з найбільшою кількістю цукерок з розчином Leetcode

Пояснення  

Припустимо, нам вводять 23. Потім ми змінюємо його на ціле число. І перетворіть його в масив цифр так само, як ми це отримали. І ми передамо вхідне значення та довжину цього вхідного значення у функцію, яку ми створили, названу комбінацією.

У цій функції ми також ініціалізували наші ключові слова string keyWords [10] = {“”, “”, “abc”, ”def”, “ghi”, “jkl”, ”mno”, “pqrs”, “tuv”, “ wxyz "}

Ми передаємо ці значення в іншу функцію, яка називається getCombination, в якій ми отримуємо вихідні дані.

Отже, ми беремо 23 як приклад, він зберігається у масиві = {2, 3} відповідно з індексом 0, 1.

Отже, тепер у функції ми оголосили чергу та список, який буде зберігати наші результати.

Ми натискаємо порожній рядок в que;
que = “”;

Введення в поки петля: ми отримуємо фронт черги в temp і видаляємо його з que,
Темп = ""

Тепер, якщо частина не виконується, оскільки значення відрізняються від temp та n. Таким чином, він виконує іншу частину, яка буде виконувати
Копія = temp.length = 0 => число [0] = 2 => клавіші [2] = “abc”
Що означає copy = “abc”;

Тепер він повторить цикл for
І додайте que в a, b і c.

Тепер він знову перевіряє while (! Que.isEmpty ()), і це правда, тому він продовжує рухатися, і він бере фронт черги в temp, який є "a", і видаляє a.
Копія = temp.length = 1 => число [1] = 3 => клавіші [3] = “def”
Тож тепер він додасть a з d, e та f і висуне його в чергу відповідно.

Тепер він знову перевіряє while (! Que.isEmpty ()), і це правда, тому він продовжує рухатися, і він бере фронт черги в temp, який зараз є “b”, і видаляє b.
Копія = temp.length = 1 => число [1] = 3 => клавіші [3] = “def”
Тож тепер він додасть b з d, e та f і висуне його в чергу відповідно.

Дивись також
Найменший підмасив з k чіткими числами

Тепер він знову перевіряє while (! Que.isEmpty ()), і це правда, тому він продовжує рухатися, і він бере фронт черги в temp, який є "c", і видаляє c.
Копія = temp.length = 1 => число [1] = 3 => клавіші [3] = “def”
Тож тепер він додасть c з d, e та f і висуне його в чергу відповідно.

Тепер, якщо це бере фронт черги в temp, це і виявляє, що temp.length дорівнює n. І додайте темп, і послідовно він буде додавати кожну отриману нами комбінацію.
І ми отримуємо результат: (ad, ae, af, bd, be, bf, cd, ce, cf)

Реалізація  

Програма C ++ для пошуку комбінацій літер телефонного номера

#include<iostream>
#include<queue>
#include<sstream>
using namespace std;

vector<string> getCombination( int inputValue[], int n, string keyWords[])
{
    vector<string> list;

    queue<string> que;
    que.push("");

    while (!que.empty())
    {
        string temp = que.front();
        que.pop();
        if (temp.length() == n)
            list.push_back(temp);
        else
            for (auto getword : keyWords[inputValue[temp.length()]])
                que.push(temp + getword);
    }

    return list;
}

void combination( int inputValue[], int n)
{

    string keyWords[10]
        = { "", "", "abc", "def", "ghi", "jkl",
            "mno", "pqrs", "tuv", "wxyz"
          };

    vector<string> list= getCombination(inputValue, n, keyWords);

    for (auto word : list)
        cout << word << " ";

    return;
}

int main()
{
    string s="23";
    stringstream comb(s);
    int le=s.length();
    int inputValue[le];
    int i=0,x=0;
    comb>>x;
    while(x>0)
    {
        inputValue[le-i-1]=x%10;
        x/=10;
        i++;
    }
    int lengths = sizeof(inputValue) / sizeof(inputValue[0]);

    combination(inputValue, lengths);
    return 0;
}
ad ae af bd be bf cd ce cf

Програма Java для пошуку комбінацій літер телефонного номера

import java.util.*;

class combinationNumber {
  static ArrayList<String> getCombination(int[] number, int n, String[] keys) {
    ArrayList<String> getList = new ArrayList<>();

    Queue<String> que = new LinkedList<>();

    que.add("");

    while (!que.isEmpty()) {
      String temp = que.remove();

      if (temp.length() == n)
        getList.add(temp);
      else {
        String copy = keys[number[temp.length()]];
        for (int i = 0; i<copy.length(); i++) {
          que.add(temp + copy.charAt(i));
        }
      }
    }
    return getList;
  }

  static void combination(int[] inputValue, int n) {
    String[] keyWords = {
      "", "", "abc", "def", "ghi", "jkl",
      "mno", "pqrs", "tuv", "wxyz"
    };

    ArrayList<String> output = getCombination(inputValue, n, keyWords);

    for (int i = 0; i<output.size(); i++) {
      System.out.print(output.get(i) + " ");
    }
  }

  public static void main(String args[]) {
    String s = "23";
    int numb = Integer.valueOf(s);
    int i = 0;
    int[] inputValue = new int[s.length()];
    while (numb > 0) {
      inputValue[s.length() - i - 1] = numb % 10;
      numb /= 10;
      i++;
    }

    int lengths = inputValue.length;
    combination(inputValue, lengths);
  }
}
ad ae af bd be bf cd ce cf

Аналіз складності  

Складність часу

O (3N × 4M) де N - кількість цифр, яким призначено 3 літери (напр .: 2,3,4), а M - кількість цифр, яким присвоєно 4 букви (напр .: 7,9).

Дивись також
Рішення номера стовпця таблиці Excel Рішення штрих-коду

Складність простору

O (3N × 4M) де N - кількість цифр, яким призначено 3 літери (напр .: 2,3,4), а M - кількість цифр, яким присвоєно 4 букви (напр .: 7,9).