ابحث عن جميع السلاسل التي تطابق نمطًا معينًا في القاموس

جربه على ممارسة GfG

#practiceLinkDiv { العرض: لا شيء! مهم؛ }

بالنظر إلى قاموس الكلمات، ابحث عن جميع السلاسل التي تتطابق مع النمط المحدد حيث يتم تعيين كل حرف في النمط بشكل فريد إلى حرف في القاموس.

أمثلة:

  Input:    dict = ['abb' 'abc' 'xyz' 'xyy']; pattern = 'foo'   Output:   [xyy abb] xyy and abb have same character at index 1 and 2 like the pattern   Input:   dict = ['abb' 'abc' 'xyz' 'xyy']; pat = 'mno'   Output:   [abc xyz] abc and xyz have all distinct characters similar to the pattern.   Input:    dict = ['abb' 'abc' 'xyz' 'xyy']; pattern = 'aba'   Output:   [] Pattern has same character at index 0 and 2. No word in dictionary follows the pattern.   Input:    dict = ['abab' 'aba' 'xyz' 'xyx']; pattern = 'aba'   Output:   [aba xyx] aba and xyx have same character at index 0 and 2 like the pattern

Recommended Practice تطابق نمط معين جربه!

الطريقة الأولى:

يقترب: الهدف هو معرفة ما إذا كانت الكلمة لها نفس بنية النمط. يمكن أن يكون أسلوب حل هذه المشكلة هو عمل تجزئة للكلمة والنمط ومقارنة ما إذا كانا متساويين أم لا. في اللغة البسيطة، نقوم بتعيين أعداد صحيحة مختلفة للأحرف المميزة للكلمة وإنشاء سلسلة من الأعداد الصحيحة (تجزئة الكلمة) حسب حدوث حرف معين في تلك الكلمة ومن ثم مقارنتها مع تجزئة النمط.

مثال:

Word='xxyzzaabcdd' Pattern='mmnoopplfmm'   For word-:   map['x']=1; map['y']=2; map['z']=3; map['a']=4; map['b']=5; map['c']=6; map['d']=7; Hash for Word='11233445677'   For Pattern-:   map['m']=1; map['n']=2; map['o']=3; map['p']=4; map['l']=5; map['f']=6; Hash for Pattern='11233445611' Therefore in the given example Hash of word is not equal to Hash of pattern so this word is not included in the answer

الخوارزمية :

قم بتشفير النمط وفقًا للطريقة المذكورة أعلاه وقم بتخزين التجزئة المقابلة للنمط في متغير سلسلة التجزئة .

تهيئة العداد أنا = 0 والتي سوف تحدد شخصية مميزة بأعداد صحيحة مميزة.
اقرأ السلسلة وإذا لم يتم تعيين الحرف الحالي إلى عدد صحيح، فقم بتعيينه إلى قيمة العداد وزيادته.
قم بتسلسل العدد الصحيح المعين للحرف الحالي إلى سلسلة التجزئة .

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

الكود الزائف:

int i=0 Declare map for character in pattern: if(map[character]==map.end()) map[character]=i++; hash_pattern+=to_string(mp[character]) for words in dictionary: i=0; Declare map if(words.length==pattern.length) for character in words: if(map[character]==map.end()) map[character]=i++ hash_word+=to_string(map[character) if(hash_word==hash_pattern) print words

C++

    // C++ program to print all   // the strings that match the   // given pattern where every   // character in the pattern is   // uniquely mapped to a character   // in the dictionary   #include          using     namespace     std  ;   // Function to encode given string   string     encodeString  (  string     str  )   {      unordered_map   <  char       int  >     map  ;      string     res     =     ''  ;      int     i     =     0  ;      // for each character in given string      for     (  char     ch     :     str  )     {      // If the character is occurring      // for the first time assign next      // unique number to that char      if     (  map  .  find  (  ch  )     ==     map  .  end  ())      map  [  ch  ]     =     i  ++  ;      // append the number associated      // with current character into the      // output string      res     +=     to_string  (  map  [  ch  ]);      }      return     res  ;   }   // Function to print all the   // strings that match the   // given pattern where every   // character in the pattern is   // uniquely mapped to a character   // in the dictionary   void     findMatchedWords  (  unordered_set   <  string  >     dict        string     pattern  )   {      // len is length of the pattern      int     len     =     pattern  .  length  ();      // Encode the string      string     hash     =     encodeString  (  pattern  );      // for each word in the dictionary      for     (  string     word     :     dict  )     {      // If size of pattern is same as      // size of current dictionary word      // and both pattern and the word      // has same hash print the word      if     (  word  .  length  ()     ==     len      &&     encodeString  (  word  )     ==     hash  )      cout      < <     word      < <     ' '  ;      }   }   // Driver code   int     main  ()   {      unordered_set   <  string  >     dict     =     {     'abb'       'abc'        'xyz'       'xyy'     };      string     pattern     =     'foo'  ;      findMatchedWords  (  dict       pattern  );      return     0  ;   }

Java

    // Java program to print all the   // strings that match the   // given pattern where every   // character in the pattern is   // uniquely mapped to a character   // in the dictionary   import     java.io.*  ;   import     java.util.*  ;   class   GFG     {      // Function to encode given string      static     String     encodeString  (  String     str  )      {      HashMap   <  Character       Integer  >     map     =     new     HashMap   <>  ();      String     res     =     ''  ;      int     i     =     0  ;      // for each character in given string      char     ch  ;      for     (  int     j     =     0  ;     j      <     str  .  length  ();     j  ++  )     {      ch     =     str  .  charAt  (  j  );      // If the character is occurring for the first      // time assign next unique number to that char      if     (  !  map  .  containsKey  (  ch  ))      map  .  put  (  ch       i  ++  );      // append the number associated with current      // character into the output string      res     +=     map  .  get  (  ch  );      }      return     res  ;      }      // Function to print all      // the strings that match the      // given pattern where every      // character in the pattern is      // uniquely mapped to a character      // in the dictionary      static     void     findMatchedWords  (      String  []     dict       String     pattern  )      {      // len is length of the pattern      int     len     =     pattern  .  length  ();      // encode the string      String     hash     =     encodeString  (  pattern  );      // for each word in the dictionary array      for     (  String     word     :     dict  )     {      // If size of pattern is same      // as size of current      // dictionary word and both      // pattern and the word      // has same hash print the word      if     (  word  .  length  ()     ==     len      &&     encodeString  (  word  ).  equals  (  hash  ))      System  .  out  .  print  (  word     +     ' '  );      }      }      // Driver code      public     static     void     main  (  String     args  []  )      {      String  []     dict     =     {     'abb'       'abc'        'xyz'       'xyy'     };      String     pattern     =     'foo'  ;      findMatchedWords  (  dict       pattern  );      }      // This code is contributed      // by rachana soma   }

Python3

    # Python3 program to print all the    # strings that match the    # given pattern where every    # character in the pattern is    # uniquely mapped to a character    # in the dictionary    # Function to encode    # given string   def   encodeString  (  Str  ):   map   =   {}   res   =   ''   i   =   0   # For each character    # in given string    for   ch   in   Str  :   # If the character is occurring    # for the first time assign next   # unique number to that char    if   ch   not   in   map  :   map  [  ch  ]   =   i   i   +=   1   # Append the number associated    # with current character into    # the output string    res   +=   str  (  map  [  ch  ])   return   res   # Function to print all    # the strings that match the    # given pattern where every    # character in the pattern is    # uniquely mapped to a character    # in the dictionary    def   findMatchedWords  (  dict     pattern  ):   # len is length of the    # pattern    Len   =   len  (  pattern  )   # Encode the string    hash   =   encodeString  (  pattern  )   # For each word in the    # dictionary array    for   word   in   dict  :   # If size of pattern is same    # as size of current    # dictionary word and both    # pattern and the word    # has same hash print the word    if  (  len  (  word  )   ==   Len   and   encodeString  (  word  )   ==   hash  ):   print  (  word     end   =   ' '  )   # Driver code    dict   =   [  'abb'     'abc'    'xyz'     'xyy'   ]   pattern   =   'foo'   findMatchedWords  (  dict     pattern  )   # This code is contributed by avanitrachhadiya2155

    // C# program to print all the strings   // that match the given pattern where   // every character in the pattern is   // uniquely mapped to a character in the dictionary   using     System  ;   using     System.Collections.Generic  ;   public     class     GFG     {      // Function to encode given string      static     String     encodeString  (  String     str  )      {      Dictionary   <  char       int  >     map     =     new     Dictionary   <  char       int  >  ();      String     res     =     ''  ;      int     i     =     0  ;      // for each character in given string      char     ch  ;      for     (  int     j     =     0  ;     j      <     str  .  Length  ;     j  ++  )     {      ch     =     str  [  j  ];      // If the character is occurring for the first      // time assign next unique number to that char      if     (  !  map  .  ContainsKey  (  ch  ))      map  .  Add  (  ch       i  ++  );      // append the number associated with current      // character into the output string      res     +=     map  [  ch  ];      }      return     res  ;      }      // Function to print all the      // strings that match the      // given pattern where every      // character in the pattern is      // uniquely mapped to a character      // in the dictionary      static     void     findMatchedWords  (  String  []     dict       String     pattern  )      {      // len is length of the pattern      int     len     =     pattern  .  Length  ;      // encode the string      String     hash     =     encodeString  (  pattern  );      // for each word in the dictionary array      foreach  (  String     word     in     dict  )      {      // If size of pattern is same as      // size of current dictionary word      // and both pattern and the word      // has same hash print the word      if     (  word  .  Length     ==     len     &&     encodeString  (  word  ).  Equals  (  hash  ))      Console  .  Write  (  word     +     ' '  );      }      }      // Driver code      public     static     void     Main  (  String  []     args  )      {      String  []     dict     =     {     'abb'       'abc'       'xyz'       'xyy'     };      String     pattern     =     'foo'  ;      findMatchedWords  (  dict       pattern  );      }   }   // This code is contributed by 29AjayKumar

JavaScript

     <  script  >   // Javascript program to print all the   // strings that match the   // given pattern where every   // character in the pattern is   // uniquely mapped to a character   // in the dictionary      // Function to encode given string   function     encodeString  (  str  )   {      let     map     =     new     Map  ();      let     res     =     ''  ;      let     i     =     0  ;          // for each character in given string      let     ch  ;      for     (  let     j     =     0  ;     j      <     str  .  length  ;     j  ++  )     {      ch     =     str  [  j  ];          // If the character is occurring for the first      // time assign next unique number to that char      if     (  !  map  .  has  (  ch  ))      map  .  set  (  ch       i  ++  );          // append the number associated with current      // character into the output string      res     +=     map  .  get  (  ch  );      }          return     res  ;   }   // Function to print all      // the strings that match the      // given pattern where every      // character in the pattern is      // uniquely mapped to a character      // in the dictionary   function     findMatchedWords  (  dict       pattern  )   {      // len is length of the pattern      let     len     =     pattern  .  length  ;          // encode the string      let     hash     =     encodeString  (  pattern  );          // for each word in the dictionary array      for     (  let     word  =  0  ;  word   <     dict  .  length  ;  word  ++  )     {      // If size of pattern is same      // as size of current      // dictionary word and both      // pattern and the word      // has same hash print the word      if     (  dict  [  word  ].  length     ==     len      &&     encodeString  (  dict  [  word  ])     ==     (  hash  ))      document  .  write  (  dict  [  word  ]     +     ' '  );      }   }   // Driver code   let     dict  =  [  'abb'       'abc'    'xyz'       'xyy'  ];   let     pattern     =     'foo'  ;   findMatchedWords  (  dict       pattern  );   // This code is contributed by unknown2108    <  /script>

الإخراج

xyy abb

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

hash_map

الطريقة الثانية:

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

مثال:

Word='xxyzzaa' Pattern='mmnoopp' Step 1-: map['m'] = x Step 2-: 'm' is already mapped to some value check whether that value is equal to current character of word-:YES ('m' is mapped to x). Step 3-: map['n'] = y Step 4-: map['o'] = z Step 5-: 'o' is already mapped to some value check whether that value is equal to current character of word-:YES ('o' is mapped to z). Step 6-: map['p'] = a Step 7-: 'p' is already mapped to some value check whether that value is equal to current character of word-: YES ('p' is mapped to a). No contradiction so current word matches the pattern

الخوارزمية :

قم بإنشاء مصفوفة أحرف يمكننا من خلالها تعيين أحرف الأنماط مع الحرف المقابل للكلمة.

تحقق أولاً مما إذا كان طول الكلمة والنمط متساويين أم لا لا ثم تحقق من الكلمة التالية.

إذا كان الطول متساويًا، فقم باجتياز النمط وإذا لم يتم تعيين الحرف الحالي للنمط بعد، فقم بتعيينه على الحرف المقابل للكلمة.

إذا تم تعيين الحرف الحالي، فتحقق مما إذا كان الحرف الذي تم تعيينه به يساوي الحرف الحالي للكلمة.

لو لا فإن الكلمة لا تتبع النمط المعطى.

إذا كانت الكلمة تتبع النمط حتى الحرف الأخير، فقم بطباعة الكلمة.

الكود الزائف:

for words in dictionary: char arr_map[128]=0 char map_word[128]=0 if(words.length==pattern.length) for 0 to length of pattern: if(arr_map[character in pattern]==0 && map_word[character in word]==0) arr_map[character in pattern]=word[character in word] map_word[character in word]=pattern[character in pattern] else if(arr_map[character]!=word[character] ||map_word[character]!=pattern[character] ) break the loop If above loop runs successfully Print(words)

C++

    // C++ program to print all   // the strings that match the   // given pattern where every   // character in the pattern is   // uniquely mapped to a character   // in the dictionary   #include          using     namespace     std  ;   bool     check  (  string     pattern       string     word  )   {      if     (  pattern  .  length  ()     !=     word  .  length  ())      return     false  ;      char     ch  [  128  ]     =     {     0     };      char     map_word  [  128  ]  =  {     0  };      int     len     =     word  .  length  ();      for     (  int     i     =     0  ;     i      <     len  ;     i  ++  )     {      if     (  ch  [  pattern  [  i  ]]     ==     0     &&     map_word  [  word  [  i  ]     ]  ==  0  )      {      ch  [  pattern  [  i  ]]     =     word  [  i  ];      map_word  [  word  [  i  ]     ]  =  pattern  [  i  ];      }      else     if     (  ch  [  pattern  [  i  ]]     !=     word  [  i  ]     ||     map_word  [  word  [  i  ]     ]  !=  pattern  [  i  ])      return     false  ;      }      return     true  ;   }   // Function to print all the   // strings that match the   // given pattern where every   // character in the pattern is   // uniquely mapped to a character   // in the dictionary   void     findMatchedWords  (  unordered_set   <  string  >     dict        string     pattern  )   {      // len is length of the pattern      int     len     =     pattern  .  length  ();      // for each word in the dictionary      for     (  string     word     :     dict  )     {      if     (  check  (  pattern       word  ))      cout      < <     word      < <     ' '  ;      }   }   // Driver code   int     main  ()   {      unordered_set   <  string  >     dict     =     {     'abb'       'abc'       'xyz'       'xyy'       'bbb'  };      string     pattern     =     'foo'  ;      findMatchedWords  (  dict       pattern  );      return     0  ;   }   // This code is contributed by Ankur Goel And Priobrata Malik

Java

    // Java program to print all   // the strings that match the   // given pattern where every   // character in the pattern is   // uniquely mapped to a character   // in the dictionary   import     java.util.*  ;      class   GFG   {      static     boolean     check  (  String     pattern       String     word  )      {      if     (  pattern  .  length  ()     !=     word  .  length  ())      return     false  ;      int  []     ch     =     new     int  [  128  ]  ;      int     Len     =     word  .  length  ();      for  (  int     i     =     0  ;     i      <     Len  ;     i  ++  )      {      if     (  ch  [  (  int  )  pattern  .  charAt  (  i  )  ]     ==     0  )      {      ch  [  (  int  )  pattern  .  charAt  (  i  )  ]     =     word  .  charAt  (  i  );      }      else     if     (  ch  [  (  int  )  pattern  .  charAt  (  i  )  ]     !=     word  .  charAt  (  i  ))      {      return     false  ;      }      }      return     true  ;      }      // Function to print all the      // strings that match the      // given pattern where every      // character in the pattern is      // uniquely mapped to a character      // in the dictionary      static     void     findMatchedWords  (  HashSet   <  String  >     dict       String     pattern  )      {      // len is length of the pattern      int     Len     =     pattern  .  length  ();      // For each word in the dictionary      String     result     =     ' '  ;      for  (  String     word     :     dict  )      {      if     (  check  (  pattern       word  ))      {      result     =     word     +     ' '     +     result  ;      }      }      System  .  out  .  print  (  result  );      }      // Driver code       public     static     void     main  (  String  []     args  )     {      HashSet   <  String  >     dict     =     new     HashSet   <  String  >  ();      dict  .  add  (  'abb'  );      dict  .  add  (  'abc'  );      dict  .  add  (  'xyz'  );      dict  .  add  (  'xyy'  );      String     pattern     =     'foo'  ;      findMatchedWords  (  dict       pattern  );      }   }   // This code is contributed by divyeshrabadiya07

Python3

    # Python3 program to print all   # the strings that match the   # given pattern where every   # character in the pattern is   # uniquely mapped to a character   # in the dictionary   def   check  (  pattern     word  ):   if   (  len  (  pattern  )   !=   len  (  word  )):   return   False   ch   =   [  0   for   i   in   range  (  128  )]   Len   =   len  (  word  )   for   i   in   range  (  Len  ):   if   (  ch  [  ord  (  pattern  [  i  ])]   ==   0  ):   ch  [  ord  (  pattern  [  i  ])]   =   word  [  i  ]   else   if   (  ch  [  ord  (  pattern  [  i  ])]   !=   word  [  i  ]):   return   False   return   True   # Function to print all the   # strings that match the   # given pattern where every   # character in the pattern is   # uniquely mapped to a character   # in the dictionary   def   findMatchedWords  (  Dict     pattern  ):   # len is length of the pattern   Len   =   len  (  pattern  )   # For each word in the dictionary   for   word   in   range  (  len  (  Dict  )   -   1     -  1     -  1  ):   if   (  check  (  pattern     Dict  [  word  ])):   print  (  Dict  [  word  ]   end   =   ' '  )   # Driver code   Dict   =   [   'abb'     'abc'     'xyz'     'xyy'   ]   pattern   =   'foo'   findMatchedWords  (  Dict     pattern  )   # This code is contributed by rag2127

    // C# program to print all   // the strings that match the   // given pattern where every   // character in the pattern is   // uniquely mapped to a character   // in the dictionary   using     System  ;   using     System.Collections  ;      using     System.Collections.Generic  ;      class     GFG  {       static     bool     check  (  string     pattern       string     word  )   {          if     (  pattern  .  Length     !=     word  .  Length  )      return     false  ;          int  []     ch     =     new     int  [  128  ];      int     Len     =     word  .  Length  ;          for  (  int     i     =     0  ;     i      <     Len  ;     i  ++  )      {      if     (  ch  [(  int  )  pattern  [  i  ]]     ==     0  )      {      ch  [(  int  )  pattern  [  i  ]]     =     word  [  i  ];      }      else     if     (  ch  [(  int  )  pattern  [  i  ]]     !=     word  [  i  ])      {      return     false  ;      }      }      return     true  ;   }   // Function to print all the   // strings that match the   // given pattern where every   // character in the pattern is   // uniquely mapped to a character   // in the dictionary   static     void     findMatchedWords  (  HashSet   <  string  >     dict        string     pattern  )   {          // len is length of the pattern      int     Len     =     pattern  .  Length  ;          // For each word in the dictionary      string     result     =     ' '  ;      foreach  (  string     word     in     dict  )      {      if     (  check  (  pattern       word  ))      {      result     =     word     +     ' '     +     result  ;      }      }      Console  .  Write  (  result  );   }   // Driver Code    static     void     Main  ()   {      HashSet   <  string  >     dict     =     new     HashSet   <  string  >  (      new     string  []{     'abb'       'abc'       'xyz'       'xyy'     });          string     pattern     =     'foo'  ;          findMatchedWords  (  dict       pattern  );   }   }   // This code is contributed by divyesh072019

JavaScript

     <  script  >   // Javascript program to print all   // the strings that match the   // given pattern where every   // character in the pattern is   // uniquely mapped to a character   // in the dictionary   function     check  (  pattern       word  )   {      if     (  pattern  .  length     !=     word  .  length  )      return     false  ;          let     ch     =     new     Array  (  128  );      for  (  let     i  =  0  ;  i   <  128  ;  i  ++  )      {      ch  [  i  ]  =  0  ;      }      let     Len     =     word  .  length  ;          for  (  let     i     =     0  ;     i      <     Len  ;     i  ++  )      {      if     (  ch  [  pattern  [  i  ].  charCodeAt  (  0  )]     ==     0  )      {      ch  [  pattern  [  i  ].  charCodeAt  (  0  )]     =     word  [  i  ];      }      else     if     (  ch  [  pattern  [  i  ].  charCodeAt  (  0  )]     !=     word  [  i  ])      {      return     false  ;      }      }      return     true  ;   }   // Function to print all the      // strings that match the      // given pattern where every      // character in the pattern is      // uniquely mapped to a character      // in the dictionary   function     findMatchedWords  (  dict    pattern  )   {      // len is length of the pattern      let     Len     =     pattern  .  length  ;          // For each word in the dictionary      let     result     =     ' '  ;      for  (  let     word     of     dict  .  values  ())      {      if     (  check  (  pattern       word  ))      {      result     =     word     +     ' '     +     result  ;      }      }      document  .  write  (  result  );   }   // Driver code   let     dict     =     new     Set  ();   dict  .  add  (  'abb'  );   dict  .  add  (  'abc'  );   dict  .  add  (  'xyz'  );   dict  .  add  (  'xyy'  );   let     pattern     =     'foo'  ;   findMatchedWords  (  dict       pattern  );   // This code is contributed by patel2127    <  /script>