Dado un patrón ‘ patrón ‘ y una oración ‘ s ‘, la tarea es verificar si las palabras en la oración dada ocurren según el patrón representado en el ‘ patrón ‘.
Ejemplos :
Entrada : patrón = “abba”, s = “geeks para para geeks”
Salida : verdadero
Explicación : en el patrón, ‘a’ denota ‘geeks’ y ‘b’ denota ‘for’. Por lo tanto, la oración ‘s’ sigue el patrón ‘patrón’Entrada : patrón = «abc», s = «geeks para geeks»
Salida : falso
Enfoque : El problema dado se puede resolver generalizando el patrón formado por las palabras en una oración dada y los caracteres en el patrón dado . Luego, simplemente verifique si tanto el patrón generalizado como el patrón dado son iguales o no. Siga los pasos a continuación para resolver el problema:
- Cree un mapa para almacenar cada palabra y asigne un valor a cada palabra única en función de su aparición .
- Ejemplo: para la oración “geeks for for geeks”, el mapa será [{“geeks”, 0}, {“for”, 1}]
- De manera similar, mapee la aparición de cada carácter en el patrón
- Luego haga coincidir el patrón índice por índice en ambos mapas e imprima el resultado
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; // Function to check if the words in given // sentence follows the given pattern bool wordPattern(string pattern, string s) { // Stores the occurrence of each word // of a sentence map<string, int> mp; int ch = -1; string temp = ""; string str = "", p = ""; for (int i = 0; i < s.length(); i++) { if (s[i] == ' ') { if (!temp.empty() && mp.find(temp) == mp.end()) { mp.insert({ temp, ++ch }); } if (mp.find(temp) != mp.end()) str += ((char)((mp.find(temp))->second + 'a')); temp = ""; } else temp += s[i]; } if (!temp.empty() && mp.find(temp) == mp.end()) mp.insert({ temp, ++ch }); if (mp.find(temp) != mp.end()) str += ((char)((mp.find(temp))->second + 'a')); map<char, int> m; ch = -1; for (int i = 0; i < pattern.length(); i++) { if (m.find(pattern[i]) == m.end()) m.insert({ pattern[i], ++ch }); if (m.find(pattern[i]) != m.end()) p += ((char)((m.find(pattern[i]))->second + 'a')); } return p == str; } // Driver Code int main() { string pattern = "abba", s = "geeks for for geeks"; cout << (wordPattern(pattern, s) ? "true" : "false"); return 0; }
Java
// Java program for the above approach import java.util.*; class GFG{ // Function to check if the words in given // sentence follows the given pattern static boolean wordPattern(String pattern, String s) { // Stores the occurrence of each word // of a sentence HashMap<String, Integer> mp = new HashMap<>(); int ch = -1; String temp = ""; String str = "", p = ""; for (int i = 0; i < s.length(); i++) { if (s.charAt(i) == ' ') { if (!temp.isEmpty() && mp.containsKey(temp)) { mp.put( temp, ++ch ); } if (mp.containsKey(temp)) str += mp.get(temp) + 'a'; temp = ""; } else temp += s.charAt(i); } if (!temp.isEmpty() && mp.containsKey(temp) ) mp.put( temp, ++ch ); if (mp.containsKey(temp)) str += mp.get(temp) + 'a'; HashMap<Character,Integer> m = new HashMap<>(); ch = -1; for (int i = 0; i < pattern.length(); i++) { if (m.containsKey(pattern.charAt(i))) m.put( pattern.charAt(i), ++ch ); if (m.containsKey(pattern.charAt(i))) p +=m.get(pattern.charAt(i)) + 'a'; } return p == str; } // Driver Code public static void main(String[] args) { String pattern = "abba", s = "geeks for for geeks"; System.out.print((wordPattern(pattern, s) ? "true" : "false")); } } // This code is contributed by Rajput-Ji
Python3
# Python program for the above approach # Function to check if the words in given # sentence follows the given pattern def wordPattern(pattern, s): # Stores the occurrence of each word # of a sentence mp = {} ch = -1 temp = "" st = "" p = "" for i in range(0, len(s)): if (s[i] == ' '): if ((len(temp)) and (not mp.__contains__(temp))): ch += 1 mp[temp] = ch if (mp.__contains__(temp)): st += ((chr)((mp[temp]) + 97)) temp = "" else: temp += s[i] if ((len(temp)) and (not mp.__contains__(temp))): ch += 1 mp[temp] = ch if (mp.__contains__(temp)): st += ((chr)((mp[temp]) + 97)) m = {} ch = -1 for i in range(0, len(pattern)): if (not m.__contains__(pattern[i])): ch += 1 m[pattern[i]] = ch if (m.__contains__(pattern[i])): p += ((chr)(m[pattern[i]] + 97)) return p == st # Driver Code pattern = "abba" s = "geeks for for geeks" ans = wordPattern(pattern, s) print("true" if ans else "false") # This code is contributed by ninja_hattori.
C#
// C# program for the above approach using System; using System.Collections.Generic; public class GFG { // Function to check if the words in given // sentence follows the given pattern static bool wordPattern(String pattern, String s) { // Stores the occurrence of each word // of a sentence Dictionary<String, int> mp = new Dictionary<String, int>(); int ch = -1; String temp = ""; String str = "", p = ""; for (int i = 0; i < s.Length; i++) { if (s[i] == ' ') { if (temp.Length != 0 && mp.ContainsKey(temp)) { mp.Add(temp, ++ch); } if (mp.ContainsKey(temp)) str += mp[temp] + 'a'; temp = ""; } else temp += s[i]; } if (temp.Length != 0 && mp.ContainsKey(temp)) mp.Add(temp, ++ch); if (mp.ContainsKey(temp)) str += mp[temp] + 'a'; Dictionary<char, int> m = new Dictionary<char,int>(); ch = -1; for (int i = 0; i < pattern.Length; i++) { if (m.ContainsKey(pattern[i])) m.Add(pattern[i], ++ch); if (m.ContainsKey(pattern[i])) p += m[pattern[i]] + 'a'; } return p == str; } // Driver Code public static void Main(String[] args) { String pattern = "abba", s = "geeks for for geeks"; Console.Write((wordPattern(pattern, s) ? "true" : "false")); } } // This code is contributed by Rajput-Ji
Javascript
<script> // JavaScript code for the above approach // Function to check if the words in given // sentence follows the given pattern function wordPattern(pattern, s) { // Stores the occurrence of each word // of a sentence let mp = new Map(); let ch = -1; let temp = ""; let str = ""; let p = ""; for (let i = 0; i < s.length; i++) { if (s[i] == ' ') { if (temp.length != 0 && !mp.has(temp)) { ch++; mp.set(temp, ch); } if (mp.has(temp)) str += String.fromCharCode(mp.get(temp) + 'a'.charCodeAt(0)) temp = ""; } else temp += s[i]; } if (temp.length != 0 && !mp.has(temp)) { ch++; mp.set(temp, ch); } if (mp.has(temp)) str += String.fromCharCode(mp.get(temp) + 'a'.charCodeAt(0)) let m = new Map() ch = -1; for (let i = 0; i < pattern.length; i++) { if (!m.has(pattern[i])) { ch++; m.set((pattern[i], ch)); } if (m.has(pattern[i])) p += String.fromCharCode(m.get(pattern[i]) + 'a'.charCodeAt(0)); } return p != str; } // Driver Code let pattern = "abba", s = "geeks for for geeks"; document.write((wordPattern(pattern, s) ? "true" : "false")); // This code is contributed by Potta Lokesh </script>
true
Complejidad de tiempo : O (NlogN), ya que estamos insertando elementos en el mapa y encontrando valores del mapa dentro del ciclo.
Espacio auxiliar : O (N), ya que estamos usando espacio adicional para el mapa.