Etsi sanakirjasta kaikki merkkijonot, jotka vastaavat tiettyä mallia
Kokeile sitä GfG Practicessa 
#practiceLinkDiv { näyttö: ei mitään !tärkeää; }
#practiceLinkDiv { näyttö: ei mitään !tärkeää; } Hae sanasanakirjasta kaikki merkkijonot, jotka vastaavat annettua mallia, jossa jokainen kuvion merkki on yksilöllisesti kartoitettu sanakirjan merkkiin.
Esimerkkejä:
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 Yhdistä tiettyyn malliin Kokeile sitä!
Tapa 1:
Lähestyä: Tavoitteena on selvittää, onko sanalla sama rakenne kuin kuviolla. Yksi lähestymistapa tähän ongelmaan voi olla tiivistäminen sanasta ja mallista ja vertailla, ovatko ne yhtä vai eivät. Yksinkertaisella kielellä annamme erilaisia kokonaislukuja sanan eri merkkeihin ja teemme kokonaislukujen merkkijonon (sanan tiiviste) tietyn merkin esiintymisen mukaan kyseisessä sanassa ja vertaa sitä sitten kuvion hajautusarvoon.
Esimerkki:
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
Algoritmi:
- Koodaa kuvio yllä olevan lähestymistavan mukaisesti ja tallenna kuvion vastaava hash merkkijonomuuttujaan hash .
- Alusta laskuri i = 0 joka kuvaa erillisen merkin erillisillä kokonaisluvuilla.
- Lue merkkijono ja jos nykyistä merkkiä ei ole kuvattu kokonaisluvuksi, yhdistä se laskuriarvoon ja lisää sitä.
- Yhdistä nykyiseen merkkiin yhdistetty kokonaisluku muotoon hash-merkkijono .
- Lue nyt jokainen sana ja tee siitä hash käyttämällä samaa algoritmia.
- Jos nykyisen sanan tiiviste on yhtä suuri kuin mallin tiiviste, tämä sana sisällytetään lopulliseen vastaukseen.
- Luo merkkijono, jossa voimme kartoittaa kuvioiden merkit sanan vastaavan merkin kanssa.
- Tarkista ensin, onko sanan ja kuvion pituus yhtä suuri vai ei, jos ei tarkista sitten seuraava sana.
- Jos pituus on yhtä suuri, käytä kuviota läpi ja jos kuvion nykyistä merkkiä ei ole kartoitettu vielä, yhdistä se sanan vastaavaan merkin muotoon.
- Jos nykyinen merkki on kartoitettu, tarkista, onko merkki, jolla se on kartoitettu, yhtä suuri kuin sanan nykyinen merkki.
- Jos ei silloin sana ei noudata annettua kaavaa.
- Jos sana seuraa kuviota viimeiseen merkkiin asti, tulosta sana.
Pseudokoodi:
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>
Lähtö
xyy abb
Monimutkaisuusanalyysi:
Tässä "N" on sanojen lukumäärä ja "K" on sen pituus. Koska meidän on kuljetettava jokainen sana erikseen luodaksemme sen hash.
Käyttö hash_map Tietorakenne merkkien yhdistämistä varten vie tämän määrän tilaa.
Tapa 2:
Lähestyä: Keskustellaan nyt hieman käsitteellisestä lähestymistavasta, joka on vielä parempi karttojen sovellus. Sen sijaan, että tekisimme tiivisteen jokaiselle sanalle, voimme kartoittaa itse kuvion kirjaimet sanan vastaavaan kirjaimeen. Jos nykyistä merkkiä ei ole kartoitettu, yhdistä se sanan vastaavaan merkkiin ja jos se on jo kartoitettu, tarkista onko arvo, jolla se on kartoitettu aiemmin, sama kuin sanan nykyinen arvo vai ei. Alla oleva esimerkki tekee asioista helposti ymmärrettäviä.
Esimerkki:
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 Algoritmi:
Pseudokoodi:
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>
Lähtö
xyy abb
Monimutkaisuusanalyysi:
Jokaisen sanan läpikäymiseen tarvitaan aika.
Käyttö hash_map Tietorakenne merkkien yhdistämistä varten kuluttaa N tilaa.
Top Artikkelit
Luokka
Mielenkiintoisia Artikkeleita
