Камбінацыі літар тэлефоннага нумара


Узровень складанасці серада
Часта пытаюцца ў амазонка яблык Atlassian Capital One Збор дадзеных eBay facebook Google Microsoft Morgan Stanley Аракул Qualtrics Twilio Uber VMware Лабараторыі Walmart
Фанаграмы Глыбіня Першы пошук Рэкурсія Радок

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

Камбінацыі літар тэлефоннага нумара

Звярніце ўвагу, што нумар 1 тут не прызначаны

Прыклад

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

Літары, прызначаныя "2" знаходзяцца "Азбука" і "3" знаходзяцца "DEF" таму камбінацыя літар будзе "ad", "ae", "af", "bd", "be", "bf", "cd", "ce" і "cf"

Алгарытм

  1. Абвясціце а чаргу і ArrayList і радок масіў.
  2. Масіў радкоў павінен захоўваць значэнні, як дадзены радок keyWords [10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", " wxyz "};
  3. Спачатку ўпусціце пустую радок у чаргу
  4. У той час як чарга мае некаторыя значэнні, яна ітэруецца па цыкле.
  5. Захоўваеце значэнне фронту чаргі ў часовы радок
  6. Калі даўжыня часовай радкі апынецца роўнай n (якая з'яўляецца даўжынёй уваходнага значэння),
  7. Дадайце значэнне часовай радкі ў спіс.
  8. У адваротным выпадку адкрыйце цыкл, у якім значэнне радка ініцыялізуецца як копія = ключы [нумар [часовая даўжыня ()]];
  9. Дадайце часовы радок у падрадок кожнага ключавога слова (0, 1) і ўстаўце яго ў чаргу.
  10. Інтэруе над ім, пакуль у чарзе няма значэнняў.
  11. Спіс вяртанняў.

Тлумачэнне

Выкажам здагадку, што нам даюць увод як 23. Затым мы мяняем яго на цэлы лік. І пераўтварыце яго ў масіў лічбаў такім жа чынам, як мы яго атрымалі. І мы перададзім ўваходнае значэнне і даўжыню гэтага ўваходнага значэння ў функцыю, якую мы зрабілі названай у якасці камбінацыі.

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

Мы перадаем гэтыя значэнні ў іншую функцыю пад назвай getCombination, у якой атрымліваем выснову.

Такім чынам, мы возьмем 23 у якасці прыкладу, ён захоўваецца ў масіве = {2, 3} адпаведна з індэксам 0, 1.

Такім чынам, зараз у функцыі мы абвясцілі чаргу і спіс, якія будуць захоўваць нашы вынікі.

Мы ўпіхваем пусты радок у que;
que = "";

Увод у у той час як цыкл: мы атрымліваем фронт чаргі ў temp і выдаляем яго з чаргі,
Тэмп = ""

Цяпер, калі частка не выконваецца, таму што значэнні адрозніваюцца ад 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"
Такім чынам, зараз ён дадасць а з d, e і f і выштурхне яго ў чаргу адпаведна.

Цяпер ён зноў правярае while (! Que.isEmpty ()), і гэта праўда, таму ён працягвае ісці, і ён прымае фронт чаргі ў temp, які цяпер "b", і выдаляе b.
Капіяваць = temp.length = 1 => нумар [1] = 3 => клавішы [3] = "def"
Такім чынам, зараз ён дадасць b з d, e і f і выштурхне яго ў чаргу адпаведна.

Цяпер ён зноў правярае 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).

Касмічная складанасць

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