Телефон нөмірінің әріптік тіркесімдері  


Күрделілік дәрежесі орта
Жиі кіреді Amazon алма Atlassian Capital One Мәліметтер базасы еВау Facebook Google Microsoft Морган Стэнли Oracle Квалификация Twilio қиятын VMware Walmart зертханалары
Кері шегіну Тереңдікті бірінші іздеу Рекурсия String

Телефон нөмірі проблемасының әріптік тіркесімдерінде біз жол 2-ден 9-ға дейінгі сандарды қамтитын мәселе, егер әр санға бірнеше әріптер берілген болса, сол санмен бейнеленетін барлық мүмкін комбинацияларды табу керек. Нөмірдің тағайындалуы төменде берілген, ол телефон түймелері сияқты.

Телефон нөмірінің әріптік тіркесімдерітүйреуіш

Мұнда 1-ге ешқандай әріп тағайындалмағанын ескеріңіз

мысал  

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

Тағайындалған хаттар «2» болып табылады «ABC» және «3» болып табылады «DEF» сондықтан әріптер тіркесімі «ad», «ae», «af», «bd», «be», «bf», «cd», «ce» және «cf» болады.

Алгоритм  

  1. Декларация а кезек және ArrayList және жол массив.
  2. Жолдық жиым мәндерді берілген жолдық кілттер ретінде сақтауы керек [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 = “”;

А-ға кіру while цикл: біз кезектің алдыңғы жағына ауысып, оны кезден алып тастаймыз,
Темп = “”

Енді егер бөлік орындалмайды, өйткені мәндер temp және n-ден өзгеше. Сонымен, ол орындайтын басқа бөлімді орындайды
Көшіру = temp.length = 0 => сан [0] = 2 => пернелер [2] = “abc”
Бұл дегеніміз көшірме = “abc”;

Енді ол цикл үшін қайталанады
Que-ді a, b және c-ге қосыңыз.

Енді ол тағы (! Que.isEmpty ()) кезінде тексереді және бұл шындық, сондықтан ол әрі қарай жүреді және кезектің алдыңғы жағында «а» және а-ны алып тастайды.
Көшіру = temp.length = 1 => сан [1] = 3 => пернелер [3] = “def”
Сонымен, енді a, d, e және f таңбаларымен қосылып, оны кезекке тұрғызады.

Енді ол тағы (! Que.isEmpty ()) кезінде тексереді және бұл шындық, сондықтан ол әрі қарай жүреді және кезектің алдыңғы жағын қазір «b» деңгейінде алады және b-ны алып тастайды.
Көшіру = temp.length = 1 => сан [1] = 3 => пернелер [3] = “def”
Сонымен, енді ол d, e және f мәндерімен қосылып, оларды кезекке тұрғызады.

Сондай-ақ, қараңыз
K ерекше сандары бар ең кіші ішкі массив

Енді ол тағы (! Que.isEmpty ()) кезінде тексереді және бұл шындық, сондықтан ол әрі қарай жүреді және кезектің алдыңғы жағында «c» және c-ді шығарады.
Көшіру = temp.length = 1 => сан [1] = 3 => пернелер [3] = “def”
Енді ол с, 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).