logo

TechCodeview

文字列

辞書内の特定のパターンに一致するすべての文字列を検索します

辞書内の特定のパターンに一致するすべての文字列を検索します
GfG Practice で試してみる #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 特定のパターンに一致する 試してみてください!

方法 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# 
   // 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

複雑さの分析:

    時間計算量: O(N*K)。 
    ここで、「N」は単語の数、「K」は単語の長さです。ハッシュを作成するには各単語を個別にトラバースする必要があるためです。 補助スペース: の上）。 
    の使用 ハッシュマップ 文字をマッピングするためのデータ構造には、この量のスペースが必要です。

方法 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

アルゴリズム:

  1. パターンの文字を単語の対応する文字にマッピングできる文字配列を作成します。
  2. まず、単語とパターンの長さが等しいかどうかを確認します。 いいえ 次に次の単語を確認します。
  3. 長さが等しい場合はパターンをトラバースし、パターンの現在の文字がまだマッピングされていない場合は、それを単語の対応する文字にマッピングします。
  4. 現在の文字がマップされている場合は、そのマップに使用されている文字が単語の現在の文字と等しいかどうかを確認します。
  5. もし いいえ その場合、単語は指定されたパターンに従いません。
  6. 単語が最後の文字までパターンに従っている場合は、その単語を出力します。

疑似コード: 

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# 
   // 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>

出力 
xyy abb

複雑さの分析:

    時間計算量: O(N*K) ここで、「N」は単語の数、「K」は単語の長さです。 
    各単語をたどるには、これが所要時間となります。 補助スペース: の上）。
    の使用 ハッシュマップ 文字をマッピングするためのデータ構造は N スペースを消費します。


共有

あなたにおすすめ

最小 XOR 値ペア

最小 XOR 値ペア

平均と平均の差

平均と平均の差

トップ記事

カテゴリ

ブログ Java変換 数学 Java コレクション 違い Java文字列

興味深い記事