Комбинатҳои ҳарфҳои рақами телефон


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon себ Atlassian Пойтахт Яке аз Хиштҳо мехаранд Facebook Google Microsoft Morgan Stanley Oracle Qualities Тиллио Uber VMware Озмоишгоҳҳои Walmart
Бозгашт Ҷустуҷӯи аввал Барқароркунӣ сатр

Дар таркиби ҳарфҳои мушкилоти рақами телефон, мо а данд дорои рақамҳои аз 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. Массиви сатр бояд қиматҳоро ҳамчун калидҳои калидии додашуда нигоҳ дорад [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 stringWWW [10] = {"", "", abc "," def "," ghi "," jkl "," mno "," pqrs "," tuv "," wxyz ”}

Мо ин қиматҳоро дар дигар функсия бо номи getCombination мегузаронем, ки дар он натиҷа ба даст меорем.

Аз ин рӯ, мо 23-ро ҳамчун мисол мегирем, ки он дар массиви = {2, 3} мутаносибан дар индекси 0, 1 нигоҳ дошта мешавад.

Ҳамин тавр, ҳоло дар як вазифа, мо навбат ва рӯйхатеро эълон кардем, ки натиҷаи моро нигоҳ медорад.

Мо сатри холиро ба que тела медиҳем;
que = "";

Воридшавӣ ба дар ҳоле ки ҳалқа: мо пеши навбатро ба temp меорем ва онро аз que хориҷ мекунем,
Temp = ""

Ҳоло агар қисм иҷро нашавад, зеро қиматҳо аз temp ва n фарқ доранд. Ҳамин тавр, он қисми дигари иҷрошударо иҷро мекунад
Нусхабардорӣ = temp.length = 0 => рақам [0] = 2 => калидҳо [2] = “abc”
Ки маънои нусхабардорӣ = "abc" -ро дорад;

Ҳоло он барои давр такрор мешавад
Ва que-ро дар a, b ва c илова кунед.

Ҳоло он дубора ҳангоми (! Que.isEmpty ()) -ро месанҷад ва ин дуруст аст, бинобар ин идома дорад ва пеши сафро дар ҳарорати муваққатӣ "a" мегирад ва хориҷ кунед a.
Нусхабардорӣ = temp.length = 1 => рақам [1] = 3 => калидҳо [3] = “def”
Ҳамин тариқ, акнун он а-ро бо d, e ва f замима карда, онро мутаносибан ба навбат меорад.

Ҳоло он дубора ҳангоми (! Que.isEmpty ()) -ро месанҷад ва ин дуруст аст, бинобар ин идома дорад ва пеши сафро дар ҳарорате, ки ҳоло "b" аст ва хориҷ мекунад b.
Нусхабардорӣ = temp.length = 1 => рақам [1] = 3 => калидҳо [3] = “def”
Ҳамин тавр, ҳоло он б-ро бо d, e ва f илова карда, мутаносибан онро дар навбати худ пахш мекунад.

Ҳоло ин бори дигар ҳангоми (! Que.isEmpty ()) -ро месанҷад ва ин дуруст аст, бинобар ин идома дорад ва пеши сафро дар ҳарорати "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

Таҳлили мураккабӣ

Мураккабии вақт

О (3N × 4M) ки N - миқдори рақамҳое, ки ба онҳо 3 ҳарф (мисол: 2,3,4) гузошта шудааст ва M - миқдори рақамҳое, ки ба онҳо 4 ҳарф (мисол: 7,9) дода шудааст.

Мураккабии фазо

О (3N × 4M) ки N - миқдори рақамҳое, ки ба онҳо 3 ҳарф (мисол: 2,3,4) гузошта шудааст ва M - миқдори рақамҳое, ки ба онҳо 4 ҳарф (мисол: 7,9) дода шудааст.