ફોન નંબરના પત્ર સંયોજનો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન Atlassian કેપિટલ વન ડેટાબેક્સ ઇબે ફેસબુક Google માઈક્રોસોફ્ટ મોર્ગન સ્ટેન્લી ઓરેકલ ક્વોલિટિક્સ Twilio ઉબેર વીએમવેર વોલમાર્ટ લેબ્સ
બેકટ્રેકીંગ Thંડાઈ પ્રથમ શોધ રિકર્ઝન શબ્દમાળા

ફોન નંબરની સમસ્યાના લેટર સંયોજનોમાં, અમે એ શબ્દમાળા 2 થી 9. નંબરો ધરાવતાં સમસ્યા એ છે કે તે સંભવિત સંયોજનોને શોધવાની છે કે જે તે નંબર દ્વારા રજૂ થઈ શકે, જો દરેક સંખ્યામાં તેને કેટલાક અક્ષરો સોંપવામાં આવ્યા હોય. નંબરની સોંપણી નીચે આપેલ છે તે ટેલિફોન બટનોની જેમ છે.

ફોન નંબરના પત્ર સંયોજનો

નોંધ લો કે અહીં 1 ને કોઈ પત્ર સોંપેલ નથી

ઉદાહરણ

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

સોંપેલ પત્રો "2" છે "એબીસી" અને "3" છે "DEF" તેથી અક્ષરોનું સંયોજન "જાહેરાત", "એઇ", "એએફ", "બીડી", "હોઈ", "બીએફ", "સીડી", "સીઇ" અને "સીએફ" હશે

અલ્ગોરિધમ

  1. ઘોષણા કરો એ કતાર અને એક એરેલિસ્ટ અને શબ્દમાળા એરે.
  2. શબ્દમાળા એરે કિંમતોને આપેલ શબ્દમાળા કીવર્ડ્સ તરીકે સંગ્રહિત કરીશું [10] = {"", "", "એબીસી", "ડેફ", "ગી", "જેકેએલ", "એમએનઓ", "પીકર્સ", "તુવ", " wxyz ”};
  3. શરૂઆતમાં, એક કતારમાં ખાલી શબ્દમાળા દબાણ કરો
  4. જ્યારે કતારમાં તેના કેટલાક મૂલ્યો છે લૂપ પર ફરી વળવું.
  5. હંગામી શબ્દમાળા માટે કતારના આગળના મૂલ્યને સંગ્રહિત કરો
  6. જો અસ્થાયી શબ્દમાળાની લંબાઈ n ની બરાબર મળી (જે ઇનપુટ મૂલ્યની લંબાઈ છે)
  7. અસ્થાયી શબ્દમાળાની કિંમત સૂચિમાં ઉમેરો.
  8. બાકી, એક લૂપ ખોલો જેમાં શબ્દમાળા મૂલ્યને કોપી = કીઝ તરીકે પ્રારંભ કરવામાં આવે છે [સંખ્યા [કામચલાઉ લંબાઈ ()]];
  9. દરેક કીવર્ડના સબસ્ટ્રિંગ (0, 1) માં અસ્થાયી શબ્દમાળા ઉમેરો અને તેને કતારમાં દબાણ કરો.
  10. જ્યાં સુધી કતારમાં તેનામાં મૂલ્યો ન હોય ત્યાં સુધી તેના પર અવેજી થાય છે.
  11. પરત સૂચિ.

સમજૂતી

માની લો કે અમને 23 તરીકે ઇનપુટ આપવામાં આવ્યું છે. પછી આપણે તેને પૂર્ણાંકોમાં બદલીએ છીએ. આપણે તેને જે રીતે મળ્યું છે તે જ રીતે તેને અંકોની એરેમાં ફેરવો. અને આપણે ઇનપુટ મૂલ્ય અને તે ઇનપુટ મૂલ્યની લંબાઈને ફંકશનમાં પસાર કરીશું જેનું નામ આપણે મિશ્રણ તરીકે આપ્યું છે.

તે ફંક્શનમાં અમે અમારી કીવર્ડ્સ શબ્દમાળા કીવર્ડ્સ [10] = {"", "", "એબીસી", "ડેફ", "ગી", "જેકેએલ", "એમએનઓ", "પીકર્સ", "તુવ", "પ્રારંભ" કર્યા wxyz ”

આપણે આ વેલ્યુઝને ગેટકોમ્બિનેશન નામના બીજા ફંક્શનમાં પસાર કરીએ છીએ જેમાં આપણને આઉટપુટ મળે છે.

તેથી આપણે તે ઉદાહરણ તરીકે 23 લઈએ, તે અનુક્રમે 2, 3 અનુક્રમણિકામાં એરે = {0, 1. માં સંગ્રહિત થાય છે.

તેથી હવે ફંકશનમાં, અમે એક કતાર અને એક સૂચિ જાહેર કરી જે આપણું આઉટપુટ સંગ્રહ કરશે.

અમે કતારમાં ખાલી શબ્દમાળા દબાણ કરીએ છીએ;
que = “”;

માં પ્રવેશ કરવો જ્યારે લૂપ: અમે કતારના આગળના ભાગને ટેમ્પરમાં મેળવીએ છીએ અને તેને કતારથી દૂર કરીએ છીએ,
ટેમ્પ = ""

હવે જો કોઈ ભાગ એક્ઝેક્યુટ કરતો નથી કારણ કે વેલ્યુ ટેમ્પ્ટ અને એનથી અલગ છે. તેથી તે બીજા ભાગને ચલાવે છે જે કરશે
ક Copyપિ કરો = ટેમ્પ્લેન્ટ લંબાઈ = 0 => સંખ્યા [0] = 2 => કીઓ [2] = “એબીસી”
જેનો અર્થ કોપી = "એબીસી";

હવે તે લૂપ માટે ફરી વળશે
અને ક, એ, બી અને સીમાં ઉમેરો.

હવે ફરીથી તે તપાસ કરે છે જ્યારે (! Que.isEmpty ()) અને તે સાચું છે તેથી તે ચાલુ રહે છે અને તે ટેમ્પમાં કતારનો આગળનો ભાગ લે છે જે “એ” છે અને એ દૂર કરે છે.
ક Copyપિ કરો = ટેમ્પ્લેન્ટ લંબાઈ = 1 => નંબર [1] = 3 => કીઓ [3] = “ડેફ”
તેથી હવે તે ડી, ઇ અને એફ સાથે એક ઉમેરવા માટે અને અનુક્રમે કતારમાં દબાણ કરશે.

હવે ફરીથી તે ચકાસે છે જ્યારે (! Que.isEmpty ()) અને તે સાચું છે તેથી તે ચાલુ જ રહે છે અને તે ટેમ્પમાં કતારની આગળ લે છે જે હવે “b” છે અને b ને દૂર કરે છે.
ક Copyપિ કરો = ટેમ્પ્લેન્ટ લંબાઈ = 1 => નંબર [1] = 3 => કીઓ [3] = “ડેફ”
તેથી હવે તે બી, ડી અને ઇ સાથે જોડશે અને અનુક્રમે તેને કતારમાં દબાણ કરશે.

હવે ફરીથી તે તપાસ કરે છે જ્યારે (! Que.isEmpty ()) અને તે સાચું છે તેથી તે ચાલુ રહે છે અને તે ટેમ્પમાં કતારની આગળ લે છે જે “c” છે અને સી દૂર કરે છે.
ક Copyપિ કરો = ટેમ્પ્લેન્ટ લંબાઈ = 1 => નંબર [1] = 3 => કીઓ [3] = “ડેફ”
તેથી હવે તે સી, ડી અને ઇ સાથે જોડશે અને અનુક્રમે તેને કતારમાં દબાણ કરશે.

હવે જો તે ટેમ્પમાં કતારનો આગળનો ભાગ લે છે અને તે જોવા મળે છે કે ટેમ્પ. લંબાઈ n જેટલી છે. અને ટેમ્પ ઉમેરો અને અનુક્રમે તે આપણને મળતા દરેક સંયોજનને ઉમેરવા જઈ રહ્યું છે.
અને અમને આઉટપુટ મળે છે: (જાહેરાત, એઇ, એએફ, બીડી, બીએફ, સીડી, સીઇ, સીએફ)

અમલીકરણ

ફોન નંબરના લેટર સંયોજનો શોધવા માટે સી ++ પ્રોગ્રામ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (3)N × 4M) જ્યાં એન એ અંકોની સંખ્યા છે કે જેને 3 અક્ષરો (દા.ત.: 2,3,4) સોંપેલ છે અને એમ તે અંકોની સંખ્યા છે જેને 4 અક્ષરો છે (ભૂતપૂર્વ: 7,9) તેને સોંપેલ છે.

અવકાશ જટિલતા

ઓ (3)N × 4M) જ્યાં એન એ અંકોની સંખ્યા છે કે જેને 3 અક્ષરો (દા.ત.: 2,3,4) સોંપેલ છે અને એમ તે અંકોની સંખ્યા છે જેને 4 અક્ષરો છે (ભૂતપૂર્વ: 7,9) તેને સોંપેલ છે.