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


Ниво на тешкотија Медиум
Често прашувано во Амазон Јаболко Атласиан капитал Еден Бази на податоци eBay Facebook Google Мајкрософт Морган Стенли Oracle Qualtrics Twilio Uber VMware Лаборатории Walmart
Враќање назад Прво пребарување на длабочина Рекурзија Стринг

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

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

Забележете дека овде нема доделено писмо на 1

пример

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

Буквите доделени на "2" се „АБЦ“ и да "3" се „ДЕФ“ затоа комбинацијата на букви ќе биде „ad“, „ae“, „af“, „bd“, „be“, „bf“, „cd“, „ce“ и „cf“

Алгоритам

  1. Прогласи а редот и ArrayList и стринг низа.
  2. Низата со низи треба да ги зачувува вредностите како дадени string keyWords [10] = {“”, “”, “abc”, “def”, “ghi”, “jkl”, “mno”, “pqrs”, “tuv”, “ wxyz ”};
  3. Отпрвин, турнете ја празната низа во редица
  4. Додека редот има некои вредности, се повторува преку јамката.
  5. Чувајте ја вредноста на предниот ред на редот во привремена низа
  6. Ако се открие дека должината на привремената низа е еднаква на n (што е должина на влезната вредност) тогаш
  7. Додадете ја вредноста на привремената низа на списокот.
  8. Друго, отворете јамка во која вредноста на низата е иницијализирана како копија = копчиња [број [temp.length ()]];
  9. Додадете ја низата temp на поднишката на секој клучен збор (0, 1) и турнете ја во редот.
  10. Се повторува над него сè додека редицата не содржи вредности.
  11. Вратен список.

Објаснување

Да претпоставиме дека ни е даден влез како 23. Потоа го менуваме во цел број. И претворете го во низа цифри на ист начин како што го добивме. И ние ќе ја внесеме Влезната вредност и должината на таа влезна вредност во функцијата што ја направивме именувана како комбинација.

Во таа функција, ние исто така ги иницијализиравме нашите клучни зборови string keyWords [10] = {“”, “”, “abc”, ”def”, “ghi”, “jkl”, ”mno”, “pqrs”, “tuv”, “ wxyz ”}

Овие вредности ги поминуваме во друга функција наречена getCombination во која го добиваме излезот.

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

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

Ние туркаме празна низа во que;
que = “”;

Внесување во А. додека јамка: го влегуваме предниот ред на редицата во темпорална и ја отстрануваме од que,
Темп = ""

Сега ако некој дел не се изврши затоа што вредностите се различни од temp и n. Значи, тој извршува друг дел што ќе го стори тоа
Копирај = temp.length = 0 => број [0] = 2 => копчиња [2] = „abc“
Што значи копија = „abc“;

Сега ќе се повтори за јамка
И додадете ги que во a, b и c.

Сега повторно проверува додека (! Que.isEmpty ()) и тоа е вистина, така што продолжува да оди и го зема предниот ред на редицата што е „а“ и отстранете a.
Копирај = временска должина = 1 => број [1] = 3 => копчиња [3] = „деф“
Па сега, ќе се додадат a со d, e и f и ќе се поттикнат во редица, соодветно.

Сега повторно проверува додека (! Que.isEmpty ()) и тоа е вистина, така што продолжува да оди и го чека редицата пред темпирање што е сега „b“ и отстранете го b.
Копирај = временска должина = 1 => број [1] = 3 => копчиња [3] = „деф“
Така, сега ќе се додадат б со d, e и f и ќе го поттикнат во редица, соодветно.

Сега повторно проверува додека (! Que.isEmpty ()) и тоа е вистина, така што продолжува да оди и го зема предниот ред на редицата што е „c“ и го отстранува c.
Копирај = временска должина = 1 => број [1] = 3 => копчиња [3] = „деф“
Па сега, ќе додаде приклучок c со d, e и f и ќе го турне во редица, соодветно.

Сега, ако застане редицата пред temp и открие дека temp. должината е еднаква на n. И додајте го темпорот и последователно ќе ја додаде секоја комбинација што ја добиваме.
И го добиваме излезот: (реклама, ае, аф, бд, биди, бф, цд, це, цф)

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

Програма 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

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

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 4 фунтиM) каде N е бројот на цифри кои имаат 3 букви (пр: 2,3,4) доделени на тоа и M е бројот на цифри кои имаат 4 букви (пр. 7,9) доделени на него.

Комплексноста на просторот

О (3N 4 фунтиM) каде N е бројот на цифри кои имаат 3 букви (пр: 2,3,4) доделени на тоа и M е бројот на цифри кои имаат 4 букви (пр. 7,9) доделени на него.