Հեռախոսահամարի նամակների համակցություններ  


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon խնձոր Atlassian Capital One Տվյալների շտեմարաններ eBay facebook Google Microsoft Morgan Stanley Պատգամախոս Քվեարկողներ Twilio Uber VMware Walmart Labs
Հետադարձ կապ Խորությունը առաջին որոնում Ռեկուրսիա String

Հեռախոսահամարի խնդրի տառային համակցություններում մենք տվել ենք ա լարային 2-ից 9 թվեր պարունակող: Խնդիրն այն է, գտնել բոլոր հնարավոր համադրությունները, որոնք կարող են ներկայացվել այդ թվով, եթե յուրաքանչյուր համար ունի իրեն նշանակված որոշ տառեր: Համարի նշանակումը տրված է դրա տակ, ճիշտ այնպես, ինչպես հեռախոսի կոճակները:

Հեռախոսահամարի նամակների համակցություններPin

Նշենք, որ այստեղ 1-ին ոչ մի նամակ չի նշանակվում

Օրինակ  

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

Նշանակված նամակները «2» են «ABC» եւ «3» են «ԴԵՖ» ուստի տառերի համադրությունը կլինի «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. Addանկում ավելացրեք ժամանակավոր տողի արժեքը:
  8. Այլապես, բացեք մի օղակ, որի մեջ տողի արժեքը սկզբնավորվում է որպես պատճեն = ստեղներ [number [temp.length ()]];
  9. Յուրաքանչյուր հիմնաբառի ենթաշարքին ավելացրեք temp տողը (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 = "";

Մտնելով ա իսկ հանգույցմենք հերթի ճակատը ստանում ենք տեմպի մեջ և հեռացնում այն ​​que- ից,
Տեմպ = «»

Հիմա եթե մի մասը չի կատարվում, քանի որ արժեքները տարբերվում են temp- ից և n- ից: Այսպիսով, այն կատարում է մեկ այլ մաս, որը կկատարի
Պատճենել = temp.length = 0 => համարը [0] = 2 => ստեղները [2] = «abc»
Ինչը նշանակում է պատճեն = "abc";

Այժմ այն ​​կրկնվելու է օղակի համար
Եվ ավելացրու հերթը a, b և c- ով:

Հիմա նորից ստուգում է while (! Que.isEmpty ()) և ճիշտ է, ուստի շարունակում է գործել և հերթ է անցնում տեմպով, որը «ա» է և հանում է a:
Պատճենել = temp.length = 1 => համարը [1] = 3 => ստեղները [3] = «def»
Այսպիսով, հիմա այն կցելու է a- ն d, e և f- ով և համապատասխանաբար հերթում է այն:

Հիմա նորից ստուգում է while (! Que.isEmpty ()) և ճիշտ է, այնպես որ շարունակում է գործել և տևում է հերթի տեմպը, որն այժմ «b» է և հեռացնում b:
Պատճենել = temp.length = 1 => համարը [1] = 3 => ստեղները [3] = «def»
Այսպիսով, այժմ այն ​​կցելու է b- ն d, e և f- ով և համապատասխանաբար հերթում է այն:

Տես նաեւ,
Ամենափոքր ենթաշերտը k հստակ թվերով

Հիմա նորից ստուգում է while (! Que.isEmpty ()) և ճիշտ է, ուստի շարունակում է գործել և հերթ է անցնում տեմպով, որը «c» է և հեռացնում c:
Պատճենել = temp.length = 1 => համարը [1] = 3 => ստեղները [3] = «def»
Այսպիսով, հիմա այն կցելու է c- ն d, e և f- ով և համապատասխանաբար հերթում է այն:

Հիմա, եթե դա տողում հերթ կանգնի և պարզի, որ տեմպի երկարությունը հավասար է 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

Բարդության վերլուծություն  

Timeամանակի բարդություն

Ո (3N × 4M) որտեղ N- ն իրեն նշանակված թվանշանների թիվն է (օրինակ `3), իսկ M- ն իրեն հատկացված թվերը` 2,3,4 տառ (օրինակ `4):

Տես նաեւ,
Excel թերթի սյունակի համարը Leetcode լուծում

Տիեզերական բարդություն

Ո (3N × 4M) որտեղ N- ն իրեն նշանակված թվանշանների թիվն է (օրինակ `3), իսկ M- ն իրեն հատկացված թվերը` 2,3,4 տառ (օրինակ `4):