Finden Sie alle Zeichenfolgen, die einem bestimmten Muster entsprechen, in einem Wörterbuch
Probieren Sie es bei GfG Practice aus 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Finden Sie anhand eines Wörterbuchs mit Wörtern alle Zeichenfolgen, die mit dem angegebenen Muster übereinstimmen, wobei jedes Zeichen im Muster eindeutig einem Zeichen im Wörterbuch zugeordnet ist.
Beispiele:
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 patternRecommended Practice Passen Sie ein bestimmtes Muster an Probieren Sie es aus!
Methode 1:
Ansatz: Ziel ist es herauszufinden, ob das Wort die gleiche Struktur wie das Muster hat. Ein Ansatz zur Lösung dieses Problems kann darin bestehen, einen Hash des Wortes und des Musters zu erstellen und zu vergleichen, ob sie gleich sind oder nicht. In einfacher Sprache weisen wir den einzelnen Zeichen des Wortes unterschiedliche Ganzzahlen zu und erstellen eine Folge von Ganzzahlen (Hash des Wortes) entsprechend dem Vorkommen eines bestimmten Zeichens in diesem Wort und vergleichen Sie es dann mit dem Hash des Musters.
Beispiel:
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
Algorithmus:
- Codieren Sie das Muster gemäß dem oben genannten Ansatz und speichern Sie den entsprechenden Hash des Musters in einer String-Variablen Hash .
- Initialisieren Sie einen Zähler ich=0 Dadurch werden unterschiedliche Zeichen unterschiedlichen Ganzzahlen zugeordnet.
- Lesen Sie die Zeichenfolge. Wenn das aktuelle Zeichen keiner Ganzzahl zugeordnet ist, ordnen Sie es dem Zählerwert zu und erhöhen Sie ihn.
- Verketten Sie die dem aktuellen Zeichen zugeordnete Ganzzahl mit dem Hash-String .
- Lesen Sie nun jedes Wort und erstellen Sie mit demselben Algorithmus einen Hash daraus.
- Wenn der Hash des aktuellen Worts mit dem Hash des Musters übereinstimmt, wird dieses Wort in die endgültige Antwort einbezogen.
- Erstellen Sie ein Zeichenarray, in dem wir die Zeichen von Mustern einem entsprechenden Zeichen eines Wortes zuordnen können.
- Überprüfen Sie zunächst, ob die Länge von Wort und Muster gleich ist oder nicht NEIN Überprüfen Sie dann das nächste Wort.
- Wenn die Länge gleich ist, wird das Muster durchlaufen, und wenn das aktuelle Zeichen des Musters noch nicht zugeordnet wurde, wird es noch dem entsprechenden Zeichen des Wortes zugeordnet.
- Wenn das aktuelle Zeichen zugeordnet ist, prüfen Sie, ob das Zeichen, mit dem es zugeordnet wurde, mit dem aktuellen Zeichen des Wortes übereinstimmt.
- Wenn NEIN dann folgt das Wort nicht dem vorgegebenen Muster.
- Wenn das Wort dem Muster bis zum letzten Zeichen folgt, wird das Wort gedruckt.
Pseudocode:
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 wordsC++
// 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>
Ausgabe
xyy abb
Komplexitätsanalyse:
Dabei ist „N“ die Anzahl der Wörter und „K“ die Länge. Da wir jedes Wort einzeln durchlaufen müssen, um seinen Hash zu erstellen.
Die Verwendung von hash_map Die Datenstruktur zum Zuordnen von Zeichen benötigt so viel Platz.
Methode 2:
Ansatz: Lassen Sie uns nun einen etwas konzeptionelleren Ansatz besprechen, der eine noch bessere Anwendung von Karten ermöglicht. Anstatt für jedes Wort einen Hash zu erstellen, können wir die Buchstaben des Musters selbst dem entsprechenden Buchstaben des Wortes zuordnen. Falls das aktuelle Zeichen nicht zugeordnet wurde, ordnen Sie es dem entsprechenden Zeichen des Wortes zu und wenn es bereits zugeordnet wurde, prüfen Sie, ob der Wert, mit dem es zuvor zugeordnet wurde, mit dem aktuellen Wert des Wortes übereinstimmt oder nicht. Das folgende Beispiel soll das Verständnis erleichtern.
Beispiel:
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 Algorithmus:
Pseudocode:
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>
Ausgabe
xyy abb
Komplexitätsanalyse:
Um jedes Wort zu durchlaufen, ist dies der Zeitbedarf.
Die Verwendung von hash_map Die Datenstruktur zum Zuordnen von Zeichen benötigt N Platz.
Das Könnte Ihnen Gefallen
Top Artikel
