Знайти всі рядки, які відповідають певному шаблону в словнику
Спробуйте на GfG Practice 
#practiceLinkDiv { display: none !important; }
#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 patternRecommended 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 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>
Вихід
xyy abb
Аналіз складності:
Тут «N» — це кількість слів, а «K» — його довжина. Оскільки нам потрібно пройти кожне слово окремо, щоб створити його хеш.
Використання hash_map структура даних для відображення символів займає таку кількість місця.
Спосіб 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# // 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
Аналіз складності:
Для проходження кожного слова буде потрібно час.
Використання hash_map структура даних для відображення символів займає N місця.
Вам Може Сподобатися
Кращі Статті
Категорія
Цікаві Статті
