දුරකථන අංකයක ලිපි සංයෝජන


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇමේසන් Apple ජංගම දුරකථන ඇට්ලසියන් ප්රාග්ධන එක් දත්ත සමුදායන් ඊ බේ ෆේස්බුක් ගූගල් මයික්රොසොෆ්ට් මෝර්ගන් ස්ටැන්ලි ඔරකල් ගුණාත්මකභාවය ට්රිලිලියෝ Uber VMware වෝල්මාර්ට් ලැබ්
පසුගාමී වීම ගැඹුර පළමු සෙවීම රචනය String

දුරකථන අංක ගැටලුවක අකුරු සංයෝජනයකදී, අපි a ලබා දී ඇත පේළියකි 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. වෙනත් නම්, පිටපත් අගය = යතුරු ලෙස ආරම්භ කරන ලද ලූපයක් විවෘත කරන්න [අංකය [temp.length ()];
  9. සෑම යතුරු පදයකම උපස්ථරයට (0, 1) තාවකාලික නූල එකතු කර එය පෝලිමේ තල්ලු කරන්න.
  10. පෝලිම්වල සාරධර්ම ඇති වන තෙක් එය ඉක්මවා යයි.
  11. ආපසු ලැයිස්තුව.

පැහැදිලි කිරීම

අපට ආදානය 23 ලෙස ලබා දී ඇතැයි සිතමු. ඉන්පසු අපි එය පූර්ණ සංඛ්‍යාවක් ලෙස වෙනස් කරමු. එය අපට ලැබී ඇති ආකාරයටම ඉලක්කම් සමූහයක් බවට පරිවර්තනය කරන්න. තවද අපි ආදාන අගය සහ එම ආදාන අගයේ දිග අපි සංයෝජනයක් ලෙස නම් කර ඇති ශ්‍රිතයට යවමු.

එම ශ්‍රිතයේ දී අපි අපගේ මූලික වචන වචන [10] = {“”, “”, “ඒබීසී”, ”ඩෙෆ්”, “ගිහී”, “ජේකේඑල්”, “ම්නෝ”, “පික්ර්ස්”, “ටුව්”, “ wxyz ”}

අපි මෙම අගයන් ලබා ගන්නේ getCombination නම් වෙනත් ශ්‍රිතයකිනි.

එබැවින් අපි 23 උදාහරණයක් ලෙස අරාව = {2, 3 in හි පිළිවෙලින් 0, 1 දර්ශකයේ ගබඩා කර ඇත.

ඉතින් දැන් ශ්‍රිතයකදී, අපි අපේ ප්‍රතිදානය ගබඩා කිරීමට යන පෝලිමක් සහ ලැයිස්තුවක් ප්‍රකාශයට පත් කළෙමු.

අපි හිස් නූලක් පෝලිමට තල්ලු කරමු;
que = “”;

ලූප අතර: අපි පෝලිමේ ඉදිරිපස කොටස තාවකාලිකව ලබාගෙන එය පෝලිමෙන් ඉවත් කරමු,
තාවකාලික = “”

දැන් කොටසක් ක්‍රියාත්මක නොවන්නේ නම් අගයන් තාවකාලික හා n ට වඩා වෙනස් වේ. එබැවින් එය වෙනත් කොටසක් ක්‍රියාත්මක කරයි
පිටපත් කරන්න = temp.length = 0 => අංකය [0] = 2 => යතුරු [2] = “abc”
එහි තේරුම copy = “abc”;

දැන් එය ලූපයක් සඳහා නැවත යෙදේ
A, b සහ c වලින් පෝලිම් එකතු කරන්න.

දැන් එය නැවත පරීක්ෂා කර බලන විට (!
පිටපත් කරන්න = 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 එකතු කර පිළිවෙලින් පෝලිමේ තල්ලු කරයි.

දැන් නැවතත් එය පරීක්ෂා කර බලන විට (!
පිටපත් කරන්න = temp.length = 1 => අංකය [1] = 3 => යතුරු [3] = “def”
දැන් එය c, d, e සහ f සමඟ එකතු කර පිළිවෙලින් පෝලිමේ තල්ලු කරයි.

දැන් එය පෝලිමේ ඉදිරිපස තාවකාලිකව ගෙන, temp.length 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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (3N × 4M) මෙහි N යනු අක්ෂර 3 ක් (උදා: 2,3,4) පවරා ඇති ඉලක්කම් ගණන වන අතර M යනු අක්ෂර 4 ක් (උදා: 7,9) පවරා ඇති ඉලක්කම් ගණන වේ.

අභ්‍යවකාශ සංකීර්ණතාව

ඕ (3N × 4M) මෙහි N යනු අක්ෂර 3 ක් (උදා: 2,3,4) පවරා ඇති ඉලක්කම් ගණන වන අතර M යනු අක්ෂර 4 ක් (උදා: 7,9) පවරා ඇති ඉලක්කම් ගණන වේ.