مجموعات الحروف من رقم الهاتف


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون أجهزة آبل Atlassian عاصمة واحدة Databricks يباي Facebook جوجل Microsoft مورجان ستانلي أوراكل Qualtrics Twilio اوبر في إم وير مختبرات وول مارت
التراجع عمق البحث الأول العودية خيط

في مجموعات الحروف الخاصة بمشكلة رقم الهاتف ، قدمنا ​​a سلسلة تحتوي على أرقام من 2 إلى 9. تكمن المشكلة في العثور على جميع التركيبات الممكنة التي يمكن تمثيلها بهذا الرقم إذا كان لكل رقم بعض الأحرف المخصصة له. يتم تعيين الرقم أدناه تمامًا مثل أزرار الهاتف.

مجموعات الحروف من رقم الهاتف

لاحظ أنه لم يتم تعيين حرف إلى 1 هنا

مثال

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

الحروف المخصصة ل "2" هي "ABC" و ل "3" هي "DEF" لذلك فإن مجموعة الأحرف ستكون "ad" و "ae" و "af" و "bd" و "be" و "bf" و "cd" و "ce" و "cf"

خوارزمية

  1. تعلن أ طابور وقائمة صفيف وسلسلة مجموعة.
  2. يجب أن تخزن مصفوفة السلاسل القيم على النحو المحدد في سلسلة keyWords [10] = {"" ، "" ، "abc" ، "def" ، "ghi" ، "jkl" ، "mno" ، "pqrs" ، "tuv" ، " wxyz "} ؛
  3. في البداية ، ادفع سلسلة فارغة إلى قائمة الانتظار
  4. بينما تحتوي قائمة الانتظار على بعض القيم فيه تتكرر عبر الحلقة.
  5. تخزين قيمة مقدمة قائمة الانتظار في سلسلة مؤقتة
  6. إذا وجد أن طول السلسلة المؤقتة يساوي n (وهو طول قيمة الإدخال)
  7. أضف قيمة السلسلة المؤقتة إلى القائمة.
  8. عدا ذلك ، افتح حلقة يتم فيها تهيئة قيمة السلسلة كنسخة = مفاتيح [رقم [temp.length ()]]؛
  9. أضف السلسلة المؤقتة إلى السلسلة الفرعية لكل كلمة رئيسية (0 ، 1) وادفعها في قائمة الانتظار.
  10. يتكرر فوقها حتى تحتوي قائمة الانتظار على قيم بداخلها.
  11. قائمة العودة.

تفسير

لنفترض أن المدخلات لدينا هي 23. ثم نقوم بتغييرها إلى عدد صحيح. وقم بتحويلها إلى مصفوفة من الأرقام بنفس الطريقة التي حصلنا عليها بها. وسنمرر قيمة الإدخال وطول قيمة الإدخال إلى الدالة التي قمنا بتسميتها كمجموعة.

في هذه الوظيفة ، قمنا أيضًا بتهيئة سلسلة كلماتنا الرئيسية keyWords [10] = {"" ، "" ، "abc" ، "def" ، "ghi" ، "jkl" ، "mno" ، "pqrs" ، "tuv" ، " wxyz "}

نقوم بتمرير هذه القيم في دالة أخرى تسمى getCombination حيث نحصل على المخرجات.

لذلك نأخذ 23 كمثال يتم تخزينها في مصفوفة = {2 ، 3} عند 0 ، 1 فهرس على التوالي.

الآن في إحدى الوظائف ، أعلنا عن قائمة انتظار وقائمة ستخزن ناتجنا.

ندفع سلسلة فارغة إلى que ؛
que = "" ؛

الدخول في حائط اللوب: نحصل على مقدمة قائمة الانتظار في درجة الحرارة ونزيلها من قائمة الانتظار ،
درجة الحرارة = ""

الآن إذا لم يتم تنفيذ جزء لأن القيم مختلفة عن temp و n. لذلك فإنه ينفذ الجزء الآخر الذي سيفعل
Copy = temp.length = 0 => number [0] = 2 => مفاتيح [2] = "abc"
وهو ما يعني copy = "abc" ؛

الآن سوف تتكرر في حلقة for
وأضف كيو في a و b و c.

الآن مرة أخرى يتحقق أثناء (! que.isEmpty ()) وهذا صحيح ، لذا فإنه يستمر ويأخذ مقدمة قائمة الانتظار في درجة الحرارة "a" وإزالة a.
Copy = temp.length = 1 => number [1] = 3 => مفاتيح [3] = "def"
والآن ستلحق a بـ d و e و f وتدفعها في قائمة الانتظار على التوالي.

الآن مرة أخرى يتحقق أثناء (! que.isEmpty ()) وهذا صحيح ، لذا فهو يستمر ويأخذ مقدمة قائمة الانتظار في درجة الحرارة "b" الآن وإزالة b.
Copy = temp.length = 1 => number [1] = 3 => مفاتيح [3] = "def"
والآن ستلحق b بـ d و e و f وتدفعها في قائمة الانتظار على التوالي.

الآن مرة أخرى يتحقق أثناء (! que.isEmpty ()) وهذا صحيح ، لذا فهو يستمر ويأخذ مقدمة قائمة الانتظار في درجة الحرارة "c" وإزالة c.
Copy = temp.length = 1 => number [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

تحليل التعقيد

تعقيد الوقت

يا (3N × 4M) حيث N هو عدد الأرقام التي تحتوي على 3 أحرف (على سبيل المثال: 2,3,4،4،7,9) و M هو عدد الأرقام التي تحتوي على XNUMX أحرف (على سبيل المثال: XNUMX،XNUMX) المخصصة لها.

تعقيد الفضاء

يا (3N × 4M) حيث N هو عدد الأرقام التي تحتوي على 3 أحرف (على سبيل المثال: 2,3,4،4،7,9) و M هو عدد الأرقام التي تحتوي على XNUMX أحرف (على سبيل المثال: XNUMX،XNUMX) المخصصة لها.