מצא את כל המחרוזות התואמות לתבנית ספציפית במילון

נסה את זה ב-GfG Practice

#practiceLinkDiv { display: none !חשוב; }

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

דוגמאות:

  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 התאם דפוס ספציפי נסה את זה!

שיטה 1:

גִישָׁה: המטרה היא למצוא האם למילה יש מבנה זהה לתבנית. גישה לבעיה זו יכולה להיות יצירת גיבוב של המילה והתבנית ולהשוות אם הם שווים או לא. בשפה פשוטה אנו מקצים מספרים שלמים שונים לתווים הנבדלים של המילה ויוצרים מחרוזת של מספרים שלמים (האש של המילה) לפי התרחשות של תו מסוים במילה הזו ולאחר מכן השוו אותו עם ה-hash של התבנית.

דוּגמָה:

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

אלגוריתם:

קודדו את התבנית לפי הגישה לעיל ואחסנו את ה-hash המתאים של התבנית במשתנה מחרוזת בְּלִיל .

אתחול מונה i=0 אשר ימפה אופי מובחן עם מספרים שלמים מובהקים.
קרא את המחרוזת ואם התו הנוכחי אינו ממופה למספר שלם מפה אותו לערך המונה והגדל אותו.
שרשור את המספר השלם שמופה לתו הנוכחי ל- מחרוזת hash .

כעת קרא כל מילה ועשה לה hash באמצעות אותו אלגוריתם.
אם ה-hash של המילה הנוכחית שווה ל-hash של התבנית אז המילה הזו נכללת בתשובה הסופית.

קוד פסאודו:

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

שיטה 2:

גִישָׁה: עכשיו בואו נדון בגישה קצת יותר מושגית שהיא יישום אפילו טוב יותר של מפות. במקום לעשות חשיש לכל מילה נוכל למפות את האותיות של התבנית עצמה עם האות המתאימה של המילה. במקרה שהתו הנוכחי לא ממופה מפה אותו לאו המתאים של המילה ואם הוא כבר ממופה אז בדקו האם הערך איתו הוא מוופה קודם לכן זהה לערך הנוכחי של המילה או לא. הדוגמה שלהלן תקל על ההבנה.

דוּגמָה:

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>