Najděte všechny řetězce, které odpovídají konkrétnímu vzoru ve slovníku
Zkuste to na GfG Practice 
#practiceLinkDiv { display: none !important; }
#practiceLinkDiv { display: none !important; } Daný slovník slov najde všechny řetězce, které odpovídají danému vzoru, přičemž každý znak ve vzoru je jednoznačně namapován na znak ve slovníku.
Příklady:
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 Přizpůsobte konkrétní vzor Zkuste to!
Metoda 1:
Přístup: Cílem je zjistit, zda má slovo stejnou strukturu jako vzor. Přístupem k tomuto problému může být vytvoření hash slova a vzoru a porovnání, zda jsou stejné nebo ne. V jednoduchém jazyce přiřadíme různá celá čísla k odlišným znakům slova a vytvoříme řetězec celých čísel (hash of the word) podle výskytu konkrétního znaku v daném slově a poté jej porovnat s hashem vzoru.
Příklad:
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
Algoritmus:
- Kódujte vzor podle výše uvedeného přístupu a uložte odpovídající hash vzoru do řetězcové proměnné hash .
- Inicializujte počítadlo i=0 který bude mapovat odlišný znak s odlišnými celými čísly.
- Přečtěte řetězec a pokud aktuální znak není namapován na celé číslo, namapujte jej na hodnotu čítače a zvyšte ji.
- Spojte celé číslo mapované na aktuální znak do hash řetězec .
- Nyní si přečtěte každé slovo a vytvořte z něj hash pomocí stejného algoritmu.
- Pokud je hash aktuálního slova stejný jako hash vzoru, je toto slovo zahrnuto do konečné odpovědi.
- Vytvořte pole znaků, ve kterém můžeme mapovat znaky vzorů s odpovídajícím znakem slova.
- Nejprve zkontrolujte, zda je délka slova a vzoru stejná nebo ne žádný pak zkontrolujte další slovo.
- Pokud je délka stejná, projeďte vzor a pokud aktuální znak vzoru ještě nebyl mapován, namapujte jej na odpovídající znak slova.
- Pokud je aktuální znak namapován, zkontrolujte, zda znak, se kterým byl namapován, se rovná aktuálnímu znaku slova.
- Li žádný pak slovo nesleduje daný vzor.
- Pokud slovo následuje vzor až do posledního znaku, vytiskněte slovo.
Pseudokód:
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>
Výstup
xyy abb
Analýza složitosti:
Zde 'N' je počet slov a 'K' je jeho délka. Protože musíme procházet každé slovo zvlášť, abychom vytvořili jeho hash.
Použití hash_map datová struktura pro mapování znaků zabírá toto množství místa.
Metoda 2:
Přístup: Nyní pojďme diskutovat o trochu koncepčnějším přístupu, který je ještě lepší aplikací map. Místo vytváření hash pro každé slovo můžeme mapovat písmena samotného vzoru s odpovídajícím písmenem slova. V případě, že aktuální znak nebyl namapován, namapujte jej na odpovídající znak slova a pokud již byl namapován, zkontrolujte, zda hodnota, se kterou byl namapován dříve, je stejná jako aktuální hodnota slova nebo ne. Níže uvedený příklad usnadní věci pochopitelné.
Příklad:
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 Algoritmus:
Pseudokód:
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>
Výstup
xyy abb
Analýza složitosti:
K procházení každého slova to bude vyžadovat čas.
Použití hash_map datová struktura pro mapování znaků zabírá N prostoru.
Mohlo By Se Vám Líbit
Nejlepší Články
Kategorie
Zajímavé Články
