Dado un diccionario de palabras, busque todas las strings que coincidan con el patrón dado donde cada carácter del patrón se asigna de forma única a un carácter en el diccionario.
Ejemplos:
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
Método 1 :
Enfoque: El objetivo es encontrar si la palabra tiene la misma estructura que el patrón. Un enfoque para este problema puede ser hacer un hash de la palabra y el patrón y comparar si son iguales o no. En lenguaje simple, asignamos diferentes números enteros a los distintos caracteres de la palabra y hacemos una string de números enteros (hash de la palabra) de acuerdo con la aparición de un carácter particular en esa palabra y luego lo comparamos con el hash del patrón.
Ejemplo:
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
Algoritmo:
- Codifique el patrón de acuerdo con el enfoque anterior y almacene el hash correspondiente del patrón en un hash de variable de string .
- Algoritmo para codificar -:
- Inicialice un contador i=0 que mapeará caracteres distintos con enteros distintos.
- Lea la string y, si el carácter actual no está asignado a un número entero, asígnelo al valor del contador e increméntelo.
- Concatene el entero asignado al carácter actual a la string hash .
- Ahora lee cada palabra y haz un hash con el mismo algoritmo.
- Si el hash de la palabra actual es igual al hash del patrón, esa palabra se incluye en la respuesta final.
Pseudocódigo:
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 <bits/stdc++.h>
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>
Producción
xyy abb
Análisis de Complejidad:
- Complejidad temporal: O(N*K).
Aquí ‘N’ es el número de palabras y ‘K’ es su longitud. Como tenemos que recorrer cada palabra por separado para crear su hash. - Espacio Auxiliar: O(N).
El uso de la estructura de datos hash_map para mapear caracteres ocupa esta cantidad de espacio.
Método 2 :
Enfoque: ahora analicemos un enfoque un poco más conceptual que es una aplicación aún mejor de los mapas. En lugar de hacer un hash para cada palabra, podemos mapear las letras del propio patrón con la letra correspondiente de la palabra. En caso de que el carácter actual no se haya mapeado, asígnelo al carácter correspondiente de la palabra y, si ya se ha mapeado, verifique si el valor con el que se mapeó anteriormente es el mismo que el valor actual de la palabra o no. . El siguiente ejemplo hará que las cosas sean fáciles de entender.
Ejemplo:
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
Algoritmo:
- Cree una array de caracteres en la que podamos asignar los caracteres de los patrones con el carácter correspondiente de una palabra.
- En primer lugar, verifique si la longitud de la palabra y el patrón son iguales o no, si no , verifique la siguiente palabra.
- Si la longitud es igual, recorra el patrón y, si el carácter actual del patrón aún no se ha asignado, asigne el carácter correspondiente de la palabra.
- Si el carácter actual está asignado, compruebe si el carácter con el que se ha asignado es igual al carácter actual de la palabra.
- Si no , entonces la palabra no sigue el patrón dado.
- Si la palabra sigue el patrón hasta el último carácter, imprima la palabra.
Pseudocódigo:
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 <bits/stdc++.h>
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>
Producción
xyy abb
Análisis de Complejidad:
- Complejidad temporal: O(N*K), donde ‘N’ es el número de palabras y ‘K’ es su longitud.
Para recorrer cada palabra, este será el requisito de tiempo. - Espacio Auxiliar: O(N).
El uso de la estructura de datos hash_map para mapear caracteres consume N espacio.
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA