ഒരു ഫോൺ നമ്പറിന്റെ കത്ത് കോമ്പിനേഷനുകൾ  


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ അത്ലഷിഅന് ക്യാപിറ്റൽ വൺ ഡാറ്റാബ്രിക്സ് ബെ ഫേസ്ബുക്ക് ഗൂഗിൾ മൈക്രോസോഫ്റ്റ് മോർഗൻ സ്റ്റാൻലി ഒറാക്കിൾ ഗുണനിലവാരം ട്വിలియో യൂബർ വിഎംവെയർ വാൾമാർട്ട് ലാബുകൾ
ബാക്ക്ട്രാക്കിംഗ് ആഴത്തിലുള്ള ആദ്യ തിരയൽ റിക്കറിഷൻ സ്ട്രിംഗ്

ഒരു ഫോൺ നമ്പർ പ്രശ്നത്തിന്റെ അക്ഷര സംയോജനത്തിൽ, ഞങ്ങൾ ഒരു നൽകി സ്ട്രിംഗ് 2 മുതൽ 9 വരെയുള്ള സംഖ്യകൾ‌ അടങ്ങിയിരിക്കുന്നു. ഓരോ നമ്പറിലും ചില അക്ഷരങ്ങൾ‌ നിശ്ചയിച്ചിട്ടുണ്ടെങ്കിൽ‌, ആ സംഖ്യയെ പ്രതിനിധീകരിക്കാൻ‌ കഴിയുന്ന എല്ലാ കോമ്പിനേഷനുകളും കണ്ടെത്തുക എന്നതാണ് പ്രശ്‌നം. ടെലിഫോൺ ബട്ടണുകൾ പോലെ തന്നെയാണ് നമ്പറിന്റെ അസൈൻമെന്റ് ചുവടെ നൽകിയിരിക്കുന്നത്.

ഒരു ഫോൺ നമ്പറിന്റെ കത്ത് കോമ്പിനേഷനുകൾമൊട്ടുസൂചി

ഇവിടെ ഒരു അക്ഷരവും നൽകിയിട്ടില്ലെന്നത് ശ്രദ്ധിക്കുക

ഉദാഹരണം  

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

നിയുക്തമാക്കിയ അക്ഷരങ്ങൾ "2" ആകുന്നു “എ ബി സി” ഒപ്പം "3" ആകുന്നു "DEF" അതിനാൽ അക്ഷരങ്ങളുടെ സംയോജനം “പരസ്യം”, “എ”, “അഫ്”, “ബിഡി”, “ആകുക”, “ബിഎഫ്”, “സിഡി”, “സിഇ”, “സിഎഫ്” എന്നിവ ആയിരിക്കും

അൽഗോരിതം  

  1. ഒരു പ്രഖ്യാപിക്കുക വരി ഒരു അറേലിസ്റ്റും സ്ട്രിംഗും ശ്രേണി.
  2. സ്‌ട്രിംഗ് കീവേഡുകൾ‌ [10] = {“”, “”, “എബിസി”, “ഡെഫ്”, “ഘി”, “ജെ‌കെ‌എൽ”, “മ്‌നോ”, “പി‌ക്ആർ‌എസ്”, “ടുവ്”, “ wxyz ”};
  3. ആദ്യം, ഒരു ശൂന്യമായ സ്ട്രിംഗ് ഒരു ക്യൂവിലേക്ക് തള്ളുക
  4. ക്യൂവിൽ ചില മൂല്യങ്ങളുണ്ടെങ്കിലും ലൂപ്പിന് മുകളിലൂടെ അത് ആവർത്തിക്കുന്നു.
  5. ക്യൂവിന്റെ മുൻവശത്തെ മൂല്യം ഒരു താൽക്കാലിക സ്‌ട്രിംഗിലേക്ക് സംഭരിക്കുക
  6. താൽ‌ക്കാലിക സ്‌ട്രിംഗിന്റെ ദൈർ‌ഘ്യം n ന് തുല്യമാണെന്ന് കണ്ടെത്തിയാൽ‌ (അത് ഇൻ‌പുട്ട് മൂല്യ ദൈർ‌ഘ്യം)
  7. ലിസ്റ്റിലേക്ക് താൽക്കാലിക സ്‌ട്രിംഗിന്റെ മൂല്യം ചേർക്കുക.
  8. അല്ലെങ്കിൽ, ഒരു ലൂപ്പ് തുറക്കുക, അതിൽ സ്ട്രിംഗ് മൂല്യം ഒരു കോപ്പി = കീകളായി സമാരംഭിക്കുന്നു [നമ്പർ [temp.length ()]];
  9. ഓരോ കീവേഡിന്റെയും സബ്‌സ്ട്രിംഗിലേക്ക് (0, 1) താൽക്കാലിക സ്‌ട്രിംഗ് ചേർത്ത് അത് ക്യൂവിലേക്ക് നീക്കുക.
  10. ക്യൂവിൽ‌ മൂല്യങ്ങൾ‌ ഉണ്ടാകുന്നതുവരെ അതിൽ‌ ആവർത്തിക്കുന്നു.
  11. റിട്ടേൺ ലിസ്റ്റ്.
ഇതും കാണുക
ഏറ്റവും വലിയ എണ്ണം കാൻഡീസ് ലീറ്റ്കോഡ് പരിഹാരമുള്ള കുട്ടികൾ

വിശദീകരണം  

നമുക്ക് ഇൻപുട്ട് 23 ആയി നൽകിയിട്ടുണ്ടെന്ന് കരുതുക. എന്നിട്ട് ഞങ്ങൾ അതിനെ ഒരു സംഖ്യയായി മാറ്റുന്നു. ഞങ്ങൾക്ക് ലഭിച്ച അതേ രീതിയിൽ അതിനെ അക്കങ്ങളുടെ ഒരു നിരയിലേക്ക് പരിവർത്തനം ചെയ്യുക. കോമ്പിനേഷനായി നാമകരണം ചെയ്ത ഫംഗ്ഷനിലേക്ക് ഇൻപുട്ട് മൂല്യവും ആ ഇൻപുട്ട് മൂല്യത്തിന്റെ ദൈർഘ്യവും ഞങ്ങൾ കൈമാറും.

ആ ഫംഗ്ഷനിൽ‌ ഞങ്ങൾ‌ കീവേഡുകൾ‌ സ്‌ട്രിംഗ് കീവേഡുകളും സമാരംഭിച്ചു [10] = {“”, “”, “എബിസി”, ”ഡെഫ്”, “ഘി”, “ജെ‌കെ‌എൽ”, “മ്‌നോ”, “പി‌ക്ആർ‌എസ്”, “ടുവ്”, “ wxyz ”}

Get ട്ട്‌പുട്ട് ലഭിക്കുന്ന getCombination എന്ന മറ്റൊരു ഫംഗ്ഷനിൽ ഞങ്ങൾ ഈ മൂല്യങ്ങൾ കൈമാറുന്നു.

അതിനാൽ ഞങ്ങൾ 23 ഉദാഹരണമായി എടുക്കുന്നു, ഇത് യഥാക്രമം 2, 3 സൂചികയിൽ അറേ = {0, 1 in ൽ സംഭരിച്ചിരിക്കുന്നു.

ഇപ്പോൾ ഒരു ഫംഗ്ഷനിൽ, ഞങ്ങളുടെ .ട്ട്‌പുട്ട് സംഭരിക്കാൻ പോകുന്ന ഒരു ക്യൂവും ലിസ്റ്റും ഞങ്ങൾ പ്രഖ്യാപിച്ചു.

ഞങ്ങൾ ഒരു ശൂന്യമായ സ്ട്രിംഗ് ക്യൂവിലേക്ക് തള്ളുന്നു;
que = “”;

A- ൽ പ്രവേശിക്കുന്നു ലൂപ്പ് സമയത്ത്: ഞങ്ങൾ‌ ക്യൂവിന്റെ മുൻ‌ഭാഗത്തെ താൽ‌ക്കാലികമാക്കി ക്യൂവിൽ‌ നിന്നും നീക്കംചെയ്യുന്നു,
താൽക്കാലികം = “”

ഇപ്പോൾ ഒരു ഭാഗം എക്സിക്യൂട്ട് ചെയ്യുന്നില്ലെങ്കിൽ മൂല്യങ്ങൾ ടെമ്പിൽ നിന്നും n ൽ നിന്നും വ്യത്യസ്തമാണ്. അതിനാൽ ഇത് ചെയ്യുന്ന മറ്റൊരു ഭാഗം എക്സിക്യൂട്ട് ചെയ്യുന്നു
പകർത്തുക = temp.length = 0 => നമ്പർ [0] = 2 => കീകൾ [2] = “abc”
ഇതിനർത്ഥം കോപ്പി = “എബിസി”;

ഇപ്പോൾ ഇത് ലൂപ്പിനായി ആവർത്തിക്കും
A, b, c എന്നിവയിൽ ക്യൂ ചേർക്കുക.

(! Que.isEmpty ()) ആയിരിക്കുമ്പോൾ ഇത് വീണ്ടും പരിശോധിക്കുന്നു, ഇത് ശരിയാണ്, അതിനാൽ ഇത് തുടരുന്നു, ഒപ്പം ക്യൂവിന്റെ മുൻവശത്തെ ടെമ്പിൽ “a” എടുക്കുകയും അത് നീക്കംചെയ്യുകയും ചെയ്യുന്നു.
പകർത്തുക = temp.length = 1 => നമ്പർ [1] = 3 => കീകൾ [3] = “def”
ഇപ്പോൾ ഇത് d, e, f എന്നിവ ഉപയോഗിച്ച് ഒരു യഥാക്രമം കൂട്ടിച്ചേർക്കുകയും അതിനെ യഥാക്രമം ക്യൂവിലേക്ക് തള്ളുകയും ചെയ്യും.

(! Que.isEmpty ()) ആയിരിക്കുമ്പോൾ ഇത് വീണ്ടും പരിശോധിക്കുന്നു, ഇത് ശരിയാണ്, അതിനാൽ ഇത് തുടരുകയാണ്, മാത്രമല്ല ക്യൂവിന്റെ മുൻഭാഗത്തെ ടെമ്പിൽ എടുക്കുകയും അത് ഇപ്പോൾ “b” ആയിരിക്കുകയും ബി നീക്കംചെയ്യുകയും ചെയ്യുന്നു.
പകർത്തുക = temp.length = 1 => നമ്പർ [1] = 3 => കീകൾ [3] = “def”
ഇപ്പോൾ ഇത് d, e, f എന്നിവ ഉപയോഗിച്ച് ബി കൂട്ടിച്ചേർക്കുകയും യഥാക്രമം ക്യൂവിലേക്ക് തള്ളുകയും ചെയ്യും.

ഇതും കാണുക
K വ്യതിരിക്തമായ നമ്പറുകളുള്ള ഏറ്റവും ചെറിയ സബ്‌റേ

(! Que.isEmpty ()) ആയിരിക്കുമ്പോൾ ഇത് വീണ്ടും പരിശോധിക്കുന്നു, ഇത് ശരിയാണ്, അതിനാൽ ഇത് തുടരുന്നു, ഒപ്പം ക്യൂവിന്റെ മുൻവശത്തെ ടെമ്പിൽ “സി” എടുക്കുകയും സി നീക്കംചെയ്യുകയും ചെയ്യുന്നു.
പകർത്തുക = temp.length = 1 => നമ്പർ [1] = 3 => കീകൾ [3] = “def”
ഇപ്പോൾ ഇത് സി, ഡി, ഇ, എഫ് എന്നിവ ഉപയോഗിച്ച് യഥാക്രമം ക്യൂവിലേക്ക് കൂട്ടിച്ചേർക്കും.

ഇപ്പോൾ അത് ക്യൂവിൽ ഫ്രണ്ട് എടുത്ത് temp.length n ന് തുല്യമാണെന്ന് കണ്ടെത്തി. ടെം‌പ് ചേർ‌ക്കുക, തുടർച്ചയായി അത് നമുക്ക് ലഭിക്കുന്ന എല്ലാ കോമ്പിനേഷനുകളും ചേർക്കുന്നു.
നമുക്ക് output ട്ട്‌പുട്ട് ലഭിക്കുന്നു: (പരസ്യം, ae, af, bd, be, bf, cd, ce, cf)

നടപ്പിലാക്കൽ  

ഒരു ഫോൺ നമ്പറിന്റെ ലെറ്റർ കോമ്പിനേഷനുകൾ കണ്ടെത്തുന്നതിനുള്ള സി ++ പ്രോഗ്രാം

#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

സങ്കീർണ്ണത വിശകലനം  

സമയ സങ്കീർണ്ണത

O (3N × 4M) ഇവിടെ N എന്നത് 3 അക്ഷരങ്ങളുള്ള (ഉദാ: 2,3,4) അക്കങ്ങളുടെ എണ്ണവും M എന്നത് 4 അക്ഷരങ്ങളുള്ള (ഉദാ: 7,9) അക്കങ്ങളുടെ എണ്ണവുമാണ്.

ഇതും കാണുക
Excel ഷീറ്റ് നിര നമ്പർ ലീട്ട്‌കോഡ് പരിഹാരം

ബഹിരാകാശ സങ്കീർണ്ണത

O (3N × 4M) ഇവിടെ N എന്നത് 3 അക്ഷരങ്ങളുള്ള (ഉദാ: 2,3,4) അക്കങ്ങളുടെ എണ്ണവും M എന്നത് 4 അക്ഷരങ്ങളുള്ള (ഉദാ: 7,9) അക്കങ്ങളുടെ എണ്ണവുമാണ്.