שילובי מכתבים של מספר טלפון  


רמת קושי בינוני
נשאל לעתים קרובות אמזון בעברית תפוח עץ Atlassian קפיטל אחד דאטבריקס eBay פייסבוק Google מיקרוסופט מורגן סטנלי אורקל Qualtrics Twilio סופר VMware מעבדות וולמארט
חזרה לאחור עומק חיפוש ראשון רקורסיה מחרוזת

בצירופי אותיות של בעיה במספר טלפון, נתנו מחרוזת המכיל מספרים מ -2 עד 9. הבעיה היא למצוא את כל הצירופים האפשריים שניתן לייצג על ידי המספר הזה אם לכל מספר מוקצות כמה אותיות. הקצאת המספר ניתנת מתחתיה בדיוק כמו כפתורי הטלפון.

שילובי מכתבים של מספר טלפון

שים לב שאין כאן אות המוקצה ל -1

דוגמה  

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

האותיות שהוקצו ל "2" יש לו "א ב ג" כדי "3" יש לו "DEF" לכן שילוב האותיות יהיה "ad", "ae", "af", "bd", "be", "bf", "cd", "ce" ו- "cf"

אַלגוֹרִיתְם  

  1. הכריז א תור וכן ArrayList ומחרוזת מערך.
  2. מערך מחרוזות צריך לאחסן את הערכים כנתון מחרוזת keyWords [10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", " W X Y Z" };
  3. בהתחלה, דחף מחרוזת ריקה לתור
  4. בעוד שהתור מכיל כמה ערכים הוא מתבצע לאורך הלולאה.
  5. אחסן את ערך חזית התור למחרוזת זמנית
  6. אם אורך המחרוזת הזמנית נמצא שווה ל- n (שהוא אורך ערך הקלט) אז
  7. הוסף את הערך של המחרוזת הזמנית לרשימה.
  8. אחרת, פתח לולאה שבה ערך המיתרים מאותחל כ העתק = מקשים [מספר [temp.length ()]];
  9. הוסף את מחרוזת הטמפ 'למזרק של כל מילת מפתח (0, 1) ודחף אותה לתור.
  10. מתבוסס מעליו עד שהתור מכיל ערכים.
  11. רשימת החזרה.
ראה גם
ילדים עם המספר הגדול ביותר של פתרונות Leetcode

הסבר  

נניח שניתן לנו קלט כ- 23. ואז נשנה אותו למספר שלם. והמירו אותו למערך ספרות באותו אופן שקיבלנו אותו. ואנחנו נעביר את ערך הקלט והאורך של ערך הקלט הזה לפונקציה שביצענו בשם כשילוב.

באותה פונקציה, אנו מאותחלים גם את מילות המפתח שלנו מחרוזת keyWords [10] = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", " W X Y Z" }

אנו מעבירים ערכים אלה בפונקציה אחרת הנקראת getCombination בה אנו מקבלים את הפלט.

אז ניקח 23 כדוגמה שהוא מאוחסן במערך = {2, 3} באינדקס 0, 1 בהתאמה.

אז עכשיו בפונקציה, הכרזנו על תור ורשימה שעומדת לאחסן את הפלט שלנו.

אנו דוחפים מחרוזת ריקה ל- que;
que = “”;

נכנסים לא תוך לולאה: אנחנו מכניסים את חזית התור לטמפ 'ומסירים אותה מ- que,
Temp = “”

עכשיו אם חלק לא מתבצע כי הערכים שונים מ- temp ו- n. אז זה מבצע חלק אחר שיעשה את
העתק = temp.length = 0 => מספר [0] = 2 => מקשים [2] = "abc"
מה שאומר העתק = "abc";

עכשיו זה יחזור לולאה
והוסף את הקו a, b ו- c.

עכשיו שוב זה בודק בזמן (! Que.isEmpty ()) וזה נכון אז זה ממשיך וזה לוקח את חזית התור בטמפ 'שהוא "a" ומסירים a.
העתק = טמפ 'אורך = 1 => מספר [1] = 3 => מקשים [3] = "def"
אז עכשיו הוא יוסיף a עם d, e ו- f וידחוף אותו בתור בהתאמה.

עכשיו זה שוב בודק בזמן (! Que.isEmpty ()) וזה נכון ולכן זה ממשיך וזה לוקח את חזית התור בטמפ 'שהוא "b" והסר b.
העתק = טמפ 'אורך = 1 => מספר [1] = 3 => מקשים [3] = "def"
אז עכשיו זה יוסיף b עם d, e ו- f וידחוף אותו בתור בהתאמה.

ראה גם
מערך המשנה הקטן ביותר עם k מספרים מובחנים

עכשיו זה שוב בודק בזמן (! Que.isEmpty ()) וזה נכון ולכן זה ממשיך וזה לוקח את חזית התור בטמפ 'שהוא "c" והסר את c.
העתק = טמפ 'אורך = 1 => מספר [1] = 3 => מקשים [3] = "def"
אז עכשיו זה יוסיף c עם d, e ו- f וידחוף אותו בתור בהתאמה.

עכשיו אם זה לוקח את החלק הקדמי של התור בטמפ 'ומצא שאורך הטמפ' שווה ל- 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

ניתוח מורכבות  

מורכבות זמן

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).