جميع مجموعات الأوتار التي يمكن استخدامها لطلب رقم

بالنظر إلى رقم طباعة كل ذلك ممكن مجموعات من السلاسل التي يمكن استخدامها لطلب الرقم المحدد في الهاتف مع المواصفات التالية. في الهاتف المحدد ، يمكننا الاتصال 2 باستخدام A أو B أو C 3 باستخدام D أو E أو F ................... 8 باستخدام T أو U أو V 9 باستخدام W أو X أو Y أو z 1 باستخدام 1 0 فقط باستخدام 0.

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

الخوارزمية:

  • قم بإنشاء خريطة التجزئة مع مفاتيح كأرقام من 0 إلى 9 والقيم كمجموعة من الأحرف المرتبطة بكل رقم.
  • تحديد وظيفة عودية printstrings التي تأخذ أربع حجج:
    أ. PHNO - رقم هاتف الإدخال
    ب. أنا - فهرس الرقم الحالي يجري معالجته
    ج. HM - خريطة التجزئة من أرقام إلى مجموعات الأحرف
    د. Str - سلسلة الأحرف التي تم إنشاؤها حتى الآن
  • داخل وظيفة printstrings:
    أ. تحقق مما إذا كنت قد وصلت إلى نهاية رقم الهاتف. إذا كانت الإجابة بنعم قم بطباعة السلسلة التي تم إنشاؤها والعودة.
    ب. احصل على مجموعة من الأحرف المرتبطة بالرقم الحالي من خريطة التجزئة.
    ج. التكرار على كل حرف في المجموعة و:
           أنا. إلحاق الحرف بالسلسلة str.
           الثاني. اتصل بشكل متكرر بوظيفة PrintStrings للرقم التالي.
          ثالثا. قم بإزالة الحرف الأخير من String Str.
  • تحديد وظيفة printstringfornumber التي تأخذ حجة واحدة:
    أ. PHNO - رقم هاتف الإدخال
  • داخل وظيفة printstringfornumber ، اتصل بوظيفة printstrings مع الوسائط phno 0 hm وسلسلة فارغة.

فيما يلي تنفيذ Java لهذه الفكرة. 

تطبيق:

C++
   // C++ program for the above approach   #include          #include         using     namespace     std  ;   void     printStrings  (  string     phNo       int     i        unordered_map   <  char       string  >     hm        string     str  )   {      if     (  i     ==     phNo  .  length  ())      {      cout      < <     str      < <     ' '  ;      return  ;      }      string     s     =     hm  [  phNo  [  i  ]];      for     (  int     j     =     0  ;     j      <     s  .  length  ();     j  ++  )      {      str  .  push_back  (  s  [  j  ]);      printStrings  (  phNo       i  +  1       hm       str  );      str  .  pop_back  ();      }   }   void     printStringForNumber  (  string     phNo  )   {      unordered_map   <  char       string  >     hm     =     {      {  '2'       'ABC'  }      {  '3'       'DEF'  }      {  '4'       'GHI'  }      {  '5'       'JKL'  }      {  '6'       'MNO'  }      {  '7'       'PQRS'  }      {  '8'       'TUV'  }      {  '9'       'WXYZ'  }      {  '1'       '1'  }      {  '0'       '0'  }      };      string     str  ;      printStrings  (  phNo       0       hm       str  );   }   int     main  ()   {      printStringForNumber  (  '23'  );      return     0  ;   }   // This code is contributed by codebraxnzt   
Java
   // Java program to print all possible key strings   // that can be used to dial a phone number.   import     java.util.HashMap  ;   class   ConvertToString   {      // A Recursive function to print all combinations      // that can be used to dial a given number.      // phNo ==> Given Phone Number      // i ==> Current digit of phNo to be processed      // hm ==> Stores characters that can be used to      // to dial a digit.      // str ==> Current output string      static     void     printStrings  (  String     phNo       int     i        HashMap   <  Character       String  >     hm        StringBuilder     str  )      {      // If all digits are processed print output      // string      if     (  i     ==     phNo  .  length  ())      {      System  .  out  .  print  (  str     +     ' '  );      return  ;      }      // Get current digit of phNo and recur for all      // characters that can be used to dial it.      String     s     =     hm  .  get  (  phNo  .  charAt  (  i  ));      for     (  int     j     =     0  ;     j      <     s  .  length  ();     j  ++  )      {      str  .  append  (  s  .  charAt  (  j  ));      printStrings  (  phNo       i  +  1       hm       str  );      str  .  deleteCharAt  (  str  .  length  ()  -  1  );      }      }      // Prints all possible combinations of strings that      // can be used to dial c[].      static     void     printStringForNumber  (  String     phNo  )      {      // Create a HashMap      HashMap   <  Character       String  >     hm     =      new     HashMap   <  Character       String  >  ();      // For every digit store characters that can      // be used to dial it.      hm  .  put  (  '2'       'ABC'  );      hm  .  put  (  '3'       'DEF'  );      hm  .  put  (  '4'       'GHI'  );      hm  .  put  (  '5'       'JKL'  );      hm  .  put  (  '6'       'MNO'  );      hm  .  put  (  '7'       'PQRS'  );      hm  .  put  (  '8'       'TUV'  );      hm  .  put  (  '9'       'WXYZ'  );      hm  .  put  (  '1'       '1'  );      hm  .  put  (  '0'       '0'  );      // Create a string to store a particular output      // string      StringBuilder     str     =     new     StringBuilder  ();      // Call recursive function      printStrings  (  phNo       0       hm       str  );      }      // Driver code to test above methods      public     static     void     main  (  String     args  []  )      {      // Prints      printStringForNumber  (  '23'  );      }   }   
Python
   def   print_strings  (  ph_no     i     hm     s  ):   if   i   ==   len  (  ph_no  ):   print  (  s     end  =  ' '  )   return   for   c   in   hm  [  ph_no  [  i  ]]:   print_strings  (  ph_no     i  +  1     hm     s  +  c  )   def   print_string_for_number  (  ph_no  ):   hm   =   {   '2'  :   'ABC'     '3'  :   'DEF'     '4'  :   'GHI'     '5'  :   'JKL'     '6'  :   'MNO'     '7'  :   'PQRS'     '8'  :   'TUV'     '9'  :   'WXYZ'     '1'  :   '1'     '0'  :   '0'   }   s   =   ''   print_strings  (  ph_no     0     hm     s  )   print_string_for_number  (  '23'  )   
C#
   using     System  ;   using     System.Collections.Generic  ;   class     Program     {      static     void     printStrings  (  string     phNo       int     i        Dictionary   <  char       string  >     hm        string     str  )      {      if     (  i     ==     phNo  .  Length  )      {      Console  .  Write  (  str     +     ' '  );      return  ;      }      string     s     =     hm  [  phNo  [  i  ]];      for     (  int     j     =     0  ;     j      <     s  .  Length  ;     j  ++  )      {      str     +=     s  [  j  ];      printStrings  (  phNo       i  +  1       hm       str  );      str     =     str  .  Remove  (  str  .  Length  -  1  );      }      }      static     void     printStringForNumber  (  string     phNo  )      {      Dictionary   <  char       string  >     hm     =     new     Dictionary   <  char       string  >      {      {  '2'       'ABC'  }      {  '3'       'DEF'  }      {  '4'       'GHI'  }      {  '5'       'JKL'  }      {  '6'       'MNO'  }      {  '7'       'PQRS'  }      {  '8'       'TUV'  }      {  '9'       'WXYZ'  }      {  '1'       '1'  }      {  '0'       '0'  }      };      string     str     =     ''  ;      printStrings  (  phNo       0       hm       str  );      }      static     void     Main  (  string  []     args  )     {      printStringForNumber  (  '23'  );      }   }   
JavaScript
   function     printStrings  (  phNo       i       hm       s  )     {      if     (  i     ===     phNo  .  length  )     {      console  .  log  (  s     +     ' '  );      return  ;      }      for     (  let     j     =     0  ;     j      <     hm  [  phNo  [  i  ]].  length  ;     j  ++  )     {      s     +=     hm  [  phNo  [  i  ]][  j  ];      printStrings  (  phNo       i  +  1       hm       s  );      s     =     s  .  slice  (  0       -  1  );      }   }   function     printStringForNumber  (  phNo  )     {      let     hm     =     {      '2'  :     'ABC'        '3'  :     'DEF'        '4'  :     'GHI'        '5'  :     'JKL'        '6'  :     'MNO'        '7'  :     'PQRS'        '8'  :     'TUV'        '9'  :     'WXYZ'        '1'  :     '1'        '0'  :     '0'      };      let     s     =     ''  ;      printStrings  (  phNo       0       hm       s  );   }   printStringForNumber  (  '23'  );   

الإخراج
AD AE AF BD BE BF CD CE CF  

تعقيد الوقت: O (2^n)  هنا ن هو طول السلسلة 

المساحة المساعدة: O (N)