Утасны дугаарын үсэг хослолууд


Хэцүү байдлын түвшин Дунд
Байнга асуудаг Амазоны Apple-ийн Atlassian Капитал Нэг Өгөгдлийн сан Ebay Facebook-ийн Google-ийн Microsoft- Morgan Stanley Oracle-ийн Qualtrics Twilio Uber 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. Мэдүүлэх a дараалал болон ArrayList ба мөр массив.
  2. String массив нь утгыг өгөгдсөн 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 = “”;

А-д орж байна while давталт: бид дарааллын урд хэсгийг түр зуур авчраад,
Темп = ""

Одоо хэсэг нь temp ба n-ээс ялгаатай тул гүйцэтгэхгүй бол. Тиймээс үүнийг хийх өөр хэсгийг гүйцэтгэдэг
Хуулбар = temp.length = 0 => тоо [0] = 2 => товчлуурууд [2] = “abc”
Энэ нь хуулах = “abc” гэсэн утгатай;

Одоо давталтад давтах болно
Que-ийг a, b, c-д нэмнэ.

Одоо дахин (! Que.isEmpty ()) - г шалгаж байгаа бөгөөд энэ нь үнэн тул үргэлжлүүлэн дарааллын урд хэсгийг "а" -тай тэнцүү болгож а-г хасах болно.
Хуулбар = temp.length = 1 => тоо [1] = 3 => товчлуурууд [3] = “def”
Тэгэхээр одоо а, d, e, f гэсэн тэмдэгтүүдийг нэмж дараалалд оруулна.

Одоо энэ нь (! Que.isEmpty ()) -ийг дахин шалгаж байгаа бөгөөд энэ нь үнэн тул үргэлжлүүлэн дарааллын урд хэсгийг одоо "b" гэсэн температурт аваад b-г хасах болно.
Хуулбар = temp.length = 1 => тоо [1] = 3 => товчлуурууд [3] = “def”
Тэгэхээр одоо d, e, f-тэй b-г нэмж дараалалд оруулна.

Одоо энэ нь (! Que.isEmpty ()) -ийг дахин шалгаж байгаа бөгөөд энэ нь үнэн тул үргэлжлүүлэн дарааллын урд хэсгийг "c" гэсэн температурт аваад c-г арилгана.
Хуулбар = temp.length = 1 => тоо [1] = 3 => товчлуурууд [3] = “def”
Тэгэхээр одоо d, e, f-тэй c-г нэмж дараалалд оруулна.

Одоо дарааллын урд хэсгийг 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) -ыг өгсөн цифрүүдийн тоо юм.