एक फोन नंबर का पत्र संयोजन


कठिनाई स्तर मध्यम
में अक्सर पूछा वीरांगना सेब Atlassian एक राजधानी डाटब्रिक्स ईबे Facebook गूगल माइक्रोसॉफ्ट मॉर्गन स्टेनली ओरेकल Qualtrics Twilio Uber VMware वॉलमार्ट लैब्स
बैक ट्रैकिंग गहराई पहली खोज Recursion तार

एक फोन नंबर समस्या के पत्र संयोजन में, हमने एक दिया है स्ट्रिंग 2 से 9 तक की संख्या। समस्या यह है कि सभी संभावित संयोजनों को ढूंढना है जो कि उस संख्या द्वारा दर्शाए जा सकते हैं यदि हर नंबर में कुछ अक्षर दिए गए हैं। नंबर का असाइनमेंट नीचे दिया गया है, यह टेलीफोन के बटनों की तरह है।

एक फोन नंबर का पत्र संयोजन

ध्यान दें कि कोई भी पत्र यहां 1 को नहीं दिया गया है

उदाहरण

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

को सौंपा गया पत्र "2" रहे "एबीसी" करने के लिए और "3" रहे "डीईएफ" इसलिए अक्षरों का संयोजन "विज्ञापन", "ae", "af", "bd", "be", "bf", "cd", "ce" और "cf" होगा।

कलन विधि

  1. डिक्लेयर ए पंक्ति और एक ArrayList और स्ट्रिंग सरणी.
  2. स्ट्रिंग सरणी को दिए गए स्ट्रिंग की-मार्क [10] = {"", "", "एबीसी", "डीआईई", "जीएचआई", "जेसीएल", "मोनो", "पॉक्सर्स", "ट्यूव" के रूप में मूल्यों को संग्रहीत करना चाहिए। डब्ल्यू एक्स वाई जेड" };
  3. सबसे पहले, एक खाली स्ट्रिंग को एक कतार में धकेलें
  4. जबकि कतार में कुछ मान हैं जो लूप के ऊपर पुनरावृत्त करता है।
  5. कतार के मोर्चे का मान एक अस्थायी स्ट्रिंग में संग्रहीत करें
  6. यदि अस्थायी स्ट्रिंग की लंबाई n के बराबर पाई जाती है (जो इनपुट मूल्य लंबाई है) तो
  7. सूची में अस्थायी स्ट्रिंग का मान जोड़ें।
  8. एल्स, एक लूप खोलें जिसमें स्ट्रिंग मान को कॉपी = कुंजियों के रूप में आरम्भ किया गया है [संख्या [temp.length ()]];
  9. प्रत्येक कीवर्ड के विकल्प (0, 1) में अस्थायी स्ट्रिंग जोड़ें और इसे कतार में धकेलें।
  10. जब तक कतार में मान नहीं होते हैं, तब तक यह उस पर निर्भर करता है।
  11. वापसी सूची।

व्याख्या

मान लीजिए हमें 23 के रूप में इनपुट दिया गया है। तब हम इसे पूर्णांक में बदलते हैं। और इसे उसी तरह से अंकों के एक सरणी में बदल दें, जैसा कि हमें मिला है। और हम उस इनपुट मान के इनपुट मान और लंबाई को उस फ़ंक्शन में पास करेंगे, जिसे हमने संयोजन के रूप में नाम दिया है।

उस समारोह में हमने अपने कीवर्ड्स स्ट्रिंग कीवर्ड्स [10] = {",", "एबीसी", "डिफ", "जीएचआई", "जेसीएल", "मोनो", "पक्र्स", "ट्यूव", "को भी इनिशियलाइज़ किया। डब्ल्यू एक्स वाई जेड" }

हम इन मूल्यों को एक अन्य फ़ंक्शन में पास करते हैं जिसे गेटकॉम्बिनेशन कहा जाता है जिसमें हम आउटपुट प्राप्त करते हैं।

तो हम एक उदाहरण के रूप में 23 लेते हैं यह क्रमशः सरणी = {2, 3} में 0, 1 सूचकांक में संग्रहीत होता है।

तो अब एक समारोह में, हमने एक कतार और एक सूची घोषित की जो हमारे आउटपुट को संग्रहीत करने जा रही है।

हम एक खाली स्ट्रिंग को कतार में धकेलते हैं;
que = "";

में प्रवेश कर रहा है घुमाव के दौरान: हम कतार के सामने अस्थायी हो जाते हैं और इसे कतार से हटा देते हैं,
अस्थायी = ""

अब अगर कोई भाग निष्पादित नहीं करता है क्योंकि मान अस्थायी और एन से अलग हैं। तो यह दूसरे भाग को निष्पादित करता है जो करेगा
कॉपी = temp.length = 0 => संख्या [0] = 2 => कुंजी [2] = "एबीसी"
जिसका अर्थ है प्रतिलिपि = "एबीसी";

अब यह लूप के लिए पुनरावृति करने वाला है
और एक, बी और सी में कतार को जोड़ें।

अब फिर से यह जाँच करता है ((! Que.isEmpty ()) और यह सच है इसलिए यह चलता रहता है और यह कतार के सामने ले जाता है जो कि "a" है और a को हटा देता है।
कॉपी = temp.length = 1 => संख्या [1] = 3 => कुंजी [3] = "डीफ़"
तो अब यह d, e और f के साथ जुड़ने वाला है और इसे क्रमशः कतार में धकेलें।

अब फिर से यह जाँच करता है ((?
कॉपी = temp.length = 1 => संख्या [1] = 3 => कुंजी [3] = "डीफ़"
तो अब यह d, e और f के साथ b को जोड़ने वाला है और क्रमशः कतार में धकेलता है।

अब फिर से यह जाँच करता है ((! Que.isEmpty ()) और यह सच है इसलिए यह चलता रहता है और यह कतार के सामने ले जाता है जो कि "c" है और c को हटा दें।
कॉपी = temp.length = 1 => संख्या [1] = 3 => कुंजी [3] = "डीफ़"
तो अब यह d, e और f के साथ c को जोड़ रहा है और क्रमशः कतार में धकेलता है।

अब अगर यह टेम्पे में कतार का मोर्चा लेता है और पाया गया कि अस्थायी। n के बराबर है। और अस्थायी जोड़ें और क्रमिक रूप से यह हमारे द्वारा प्राप्त प्रत्येक संयोजन को जोड़ने जा रहा है।
और हम आउटपुट प्राप्त करते हैं: (विज्ञापन, 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

एक फोन नंबर के पत्र संयोजन खोजने के लिए जावा प्रोग्राम

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

जटिलता विश्लेषण

समय जटिलता

ओ (३)N × 4M) जहाँ N अंकों की संख्या है, जिसके 3 अक्षर हैं (उदा: 2,3,4) इसे सौंपा गया है और M अंकों की संख्या है जिसमें 4 अक्षर हैं (उदा: 7,9)।

अंतरिक्ष जटिलता

ओ (३)N × 4M) जहाँ N अंकों की संख्या है, जिसके 3 अक्षर हैं (उदा: 2,3,4) इसे सौंपा गया है और M अंकों की संख्या है जिसमें 4 अक्षर हैं (उदा: 7,9)।