НАМЕРЕТЕ ВСИЧКИ НИЗОВЕ, КОИТО ОТГОВАРЯТ НА ОПРЕДЕЛЕН МОДЕЛ В РЕЧНИК

Опитайте в GfG Practice

#practiceLinkDiv { display: none !important; }

Даден е речник от думи, намерете всички низове, които съответстват на дадения шаблон, където всеки знак в шаблона е уникално съпоставен със знак в речника.

Примери:

  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:

Подход: Целта е да се установи дали думата има същата структура като модела. Един подход към този проблем може да бъде да се направи хеш на думата и шаблона и да се сравни дали са равни или не. На прост език присвояваме различни цели числа на отделните знаци на думата и правим низ от цели числа (разширена дума) според появата на конкретен знак в тази дума и след това го сравнете с хеша на модела.

Пример:

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

Алгоритъм:

Кодирайте шаблона според горния подход и запазете съответния хеш на шаблона в низова променлива хеш .

Инициализирайте брояч i=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

Анализ на сложността:

хеш_карта

Метод 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>