Комбинације слова телефонског броја  


Ниво тешкоће Средњи
Често питани у амазонка јабука Атлассиан Цапитал Оне Датабрицкс еБаи фацебоок гоогле мицрософт Морган Стенли пророчанство Куалтрицс Твилио Убер ВМваре Валмарт Лабс
Бацктрацкинг Дубина прва претрага Рекурзије низ

У комбинацијама слова проблема са бројем телефона дали смо а низ који садрже бројеве од 2 до 9. Проблем је у проналажењу свих могућих комбинација које би могле бити представљене тим бројем ако је сваком броју додељена нека слова. Додељивање броја дато је испод њега, баш је попут телефонских тастера.

Комбинације слова телефонског бројаПин

Имајте на уму да овде није додељено слово 1

Пример  

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

Писма додељена "КСНУМКС" су “АБЦ” и да "КСНУМКС" су „ДЕФ“ стога ће комбинација слова бити „ад“, „ае“, „аф“, „бд“, „бе“, „бф“, „цд“, „це“ и „цф“

Алгоритам  

  1. Изјавите а Ред и АрраиЛист и стринг поредак.
  2. Низ низа треба да чува вредности као задати низ кеиВордс [10] = {“”, “”, “абц”, “деф”, “гхи”, “јкл”, “мно”, “пкрс”, “тув”, “ вкиз ”};
  3. Прво гурните празан низ у ред
  4. Иако ред има неке вредности, он се понавља кроз петљу.
  5. Похраните вредност фронта реда у привремени низ
  6. Ако се утврди да је дужина привременог низа једнака н (што је дужина улазне вредности), тада
  7. Додајте вредност привременог низа на листу.
  8. У супротном, отворите петљу у којој се вредност низа иницијализује као цопи = кеис [нумбер [темп.ленгтх ()]];
  9. Додајте привремени низ у подниз сваке кључне речи (0, 1) и гурните га у ред.
  10. Интеракција над њом све док ред не садржи вредности.
  11. Листа за повратак.
Види такође
Деца са највећим бројем слаткиша са Леетцоде решењем

Објашњење  

Претпоставимо да нам се даје податак као 23. Тада га мењамо у цео број. И претворите га у низ цифара на исти начин на који смо га добили. И проследићемо улазну вредност и дужину те улазне вредности у функцију коју смо направили именовану као комбинација.

У тој функцији такође смо иницијализовали кључне речи стринг кеиВордс [10] = {“”, “”, “абц”, ”деф”, “гхи”, “јкл”, ”мно”, “пкрс”, “тув”, “ вкиз ”}

Те вредности прослеђујемо у другој функцији која се назива гетЦомбинатион у којој добијамо излаз.

Дакле, узимамо 23 као пример да се чува у низу = {2, 3} са индексом 0, 1.

Тако смо сада у функцији прогласили ред и листу која ће сачувати наш излаз.

Гурамо празан низ у куе;
куе = "";

Улазак у док петља: добијамо предњи део реда у темп и уклањамо га из реда,
Темп = ""

Сад ако се део не изврши, јер се вредности разликују од темп и н. Дакле, извршава други део који ће извршити
Копија = темп.ленгтх = 0 => број [0] = 2 => тастери [2] = “абц”
Што значи цопи = “абц”;

Сад ће поновити фор петљу
И додајте куе у а, б и ц.

Сада поново проверава вхиле (! Куе.исЕмпти ()) и тачно је, тако да наставља и узима ред реда испред у темп који је „а“ и уклања а.
Копија = темп.ленгтх = 1 => број [1] = 3 => тастери [3] = “деф”
Дакле, сад ће додати а са д, е и ф и гурнути га у ред, редом.

Сада поново проверава вхиле (! Куе.исЕмпти ()) и тачно је, тако да наставља даље и узима ред реда у темп који је сада „б“ и уклања б.
Копија = темп.ленгтх = 1 => број [1] = 3 => тастери [3] = “деф”
Дакле, сада ће додати б са д, е и ф и гурнути га у ред, редом.

Види такође
Најмањи подред са к разликовних бројева

Сада поново проверава вхиле (! Куе.исЕмпти ()) и тачно је, тако да наставља и узима ред реда испред у темп који је „ц“ и уклања ц.
Копија = темп.ленгтх = 1 => број [1] = 3 => тастери [3] = “деф”
Дакле, сад ће додати ц са д, е и ф и гурнути га у ред, редом.

Сад ако узме испред реда реда у темп то и утврди да је темп.ленгтх једнака н. И додајте темп и редом ће додавати сваку комбинацију коју добијемо.
И добијамо излаз: (ад, ае, аф, бд, бе, бф, цд, це, цф)

Имплементација  

Програм Ц ++ за проналажење комбинација слова телефонског броја

#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

Јава програм за проналажење комбинација слова телефонског броја

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

Анализа сложености  

Сложеност времена

О (3N × КСНУМКСM) где је Н број цифара којима су додељена 3 слова (нпр: 2,3,4), а М број цифара којима су додељена 4 слова (нпр: 7,9).

Види такође
Екцел Схеет Цолумн Нумбер Леетцоде решење

Сложеност простора

О (3N × КСНУМКСM) где је Н број цифара којима су додељена 3 слова (нпр: 2,3,4), а М број цифара којима су додељена 4 слова (нпр: 7,9).