Dadas dos strings S1 y S2 , la tarea es verificar si S2 contiene un anagrama de S1 como su substring .
Ejemplos:
Entrada: S1 = “ab”, S2 = “bbpobac”
Salida: Sí
Explicación: La string S2 contiene el anagrama “ba” de S1 (“ba”).Entrada: S1 = “ab”, S2 = “cbddaoo”
Salida: No
Enfoque: siga los pasos a continuación para resolver el problema:
- Inicialice dos Hashmaps s1hash y s2hash para almacenar la frecuencia de los alfabetos de las dos strings.
- Si la longitud de S1 es mayor que la longitud de S2 , imprima “NO” .
- Iterar sobre los caracteres de la string S1 y actualizar s1hash .
- Repita los caracteres de la string S2 utilizando la técnica de ventana deslizante y actualice HashMap en consecuencia.
- Para cualquier substring de S2 de longitud igual a la longitud de S1, si se encuentra que ambos Hashmaps son iguales, imprima «SÍ» .
- De lo contrario, escriba “NO” .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ Program to implement // the above approach #include <bits/stdc++.h> using namespace std; // Function to check if string s2 // contains anagram of the string // s1 as its substring bool checkAnagram(string s1, string s2) { // Stores frequencies of // characters in substrings of s2 vector<int> s2hash(26, 0); // Stores frequencies of // characters in s1 vector<int> s1hash(26, 0); int s1len = s1.size(); int s2len = s2.size(); // If length of s2 exceeds length of s1 if (s1len > s2len) return false; int left = 0, right = 0; // Store frequencies of characters in first // substring of length s1len in string s2 while (right < s1len) { s1hash[s1[right] - 'a'] += 1; s2hash[s2[right] - 'a'] += 1; right++; } right -= 1; // Perform Sliding Window technique while (right < s2len) { // If hashmaps are found to be // identical for any substring if (s1hash == s2hash) return true; right++; if (right != s2len) s2hash[s2[right] - 'a'] += 1; s2hash[s2[left] - 'a'] -= 1; left++; } return false; } // Driver Code int main() { string s1 = "ab"; string s2 = "bbpobac"; if (checkAnagram(s1, s2)) cout << "YES\n"; else cout << "No\n"; return 0; }
Java
// Java program for the above approach import java.io.*; import java.util.*; class GFG { // Function to check if string s2 // contains anagram of the string // s1 as its substring public static boolean checkAnagram(String s1, String s2) { // Stores frequencies of // characters in substrings of s2 int s2hash[] = new int[26]; // Stores frequencies of // characters in s1 int s1hash[] = new int[26]; int s1len = s1.length(); int s2len = s2.length(); // If length of s2 exceeds length of s1 if (s1len > s2len) return false; int left = 0, right = 0; // Store frequencies of characters in first // substring of length s1len in string s2 while (right < s1len) { s1hash[s1.charAt(right) - 'a'] += 1; s2hash[s2.charAt(right) - 'a'] += 1; right++; } right -= 1; // Perform Sliding Window technique while (right < s2len) { // If hashmaps are found to be // identical for any substring if (Arrays.equals(s1hash, s2hash)) return true; right++; if (right != s2len) s2hash[s2.charAt(right) - 'a'] += 1; s2hash[s2.charAt(left) - 'a'] -= 1; left++; } return false; } // Driver Code public static void main(String[] args) { String s1 = "ab"; String s2 = "bbpobac"; if (checkAnagram(s1, s2)) System.out.println("YES"); else System.out.println("No"); } } // This code is contributed by kingash.
Python3
# Python 3 Program to implement # the above approach # Function to check if string s2 # contains anagram of the string # s1 as its substring def checkAnagram(s1, s2): # Stores frequencies of # characters in substrings of s2 s2hash = [0 for i in range(26)] # Stores frequencies of # characters in s1 s1hash = [0 for i in range(26)] s1len = len(s1) s2len = len(s2) # If length of s2 exceeds length of s1 if (s1len > s2len): return False left = 0 right = 0 # Store frequencies of characters in first # substring of length s1len in string s2 while (right < s1len): s1hash[ord(s1[right]) - 97] += 1 s2hash[ord(s2[right]) - 97] += 1 right += 1 right -= 1 # Perform Sliding Window technique while (right < s2len): # If hashmaps are found to be # identical for any substring if (s1hash == s2hash): return True right += 1 if (right != s2len): s2hash[ord(s2[right]) - 97] += 1 s2hash[ord(s2[left]) - 97] -= 1 left += 1 return False # Driver Code if __name__ == '__main__': s1 = "ab" s2 = "bbpobac" if (checkAnagram(s1, s2)): print("YES") else: print("No") # This code is contributed by ipg2016107
C#
// C# Program to implement // the above approach using System; using System.Collections.Generic; class GFG{ // Function to check if string s2 // contains anagram of the string // s1 as its substring static bool checkAnagram(string s1, string s2) { // Stores frequencies of // characters in substrings of s2 List<int> s2hash = new List<int>(); for(int i=0;i<26;i++) s2hash.Add(0); // Stores frequencies of // characters in s1 List<int> s1hash = new List<int>(); for(int i=0;i<26;i++) s1hash.Add(0); int s1len = s1.Length; int s2len = s2.Length; // If length of s2 exceeds length of s1 if (s1len > s2len) return false; int left = 0, right = 0; // Store frequencies of characters in first // substring of length s1len in string s2 while (right < s1len) { s1hash[s1[right] - 'a'] += 1; s2hash[s2[right] - 'a'] += 1; right++; } right -= 1; // Perform Sliding Window technique while (right < s2len) { // If hashmaps are found to be // identical for any substring if (s1hash == s2hash) return true; right++; if(right != s2len) s2hash[s2[right] - 'a'] += 1; s2hash[s2[left] - 'a'] -= 1; left++; } return false; } // Driver Code public static void Main() { string s1 = "ab"; string s2 = "bbpobac"; if (checkAnagram(s1, s2)==true) Console.WriteLine("NO"); else Console.WriteLine("YES"); } } // This code is contributed by bgangawar59.
Javascript
<script> // Javascript Program to implement // the above approach // Function to check if string s2 // contains anagram of the string // s1 as its substring function checkAnagram(s1, s2) { // Stores frequencies of // characters in substrings of s2 var s2hash = Array(26).fill(0); // Stores frequencies of // characters in s1 var s1hash = Array(26).fill(0); var s1len = s1.length; var s2len = s2.length; // If length of s2 exceeds length of s1 if (s1len > s2len) return false; var left = 0, right = 0; // Store frequencies of characters in first // substring of length s1len in string s2 while (right < s1len) { s1hash[s1[right].charCodeAt(0) - 'a'.charCodeAt(0)] += 1; s2hash[s2[right].charCodeAt(0) - 'a'.charCodeAt(0)] += 1; right++; } right -= 1; // Perform Sliding Window technique while (right < s2len) { var ans = true; // If hashmaps are found to be // identical for any substring for(var i =0; i<26; i++) { if(s1hash[i]!=s2hash[i]) { ans = false; } } if(ans) return true; right++; if (right != s2len) s2hash[s2[right].charCodeAt(0) - 'a'.charCodeAt(0)] += 1; s2hash[s2[left].charCodeAt(0) - 'a'.charCodeAt(0)] -= 1; left++; } return false; } // Driver Code var s1 = "ab"; var s2 = "bbpobac"; if (checkAnagram(s1, s2)) document.write( "YES"); else document.write( "No"); // This code is contributed by importantly. </script>
Producción:
YES
Complejidad de Tiempo: O(26 * len(S2))
Espacio Auxiliar: O(26)