Comprobar si una string contiene un anagrama de otra string como su substring

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:
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:

  1. Inicialice dos Hashmaps s1hash y s2hash para almacenar la frecuencia de los alfabetos de las dos strings.
  2. Si la longitud de S1 es mayor que la longitud de S2 , imprima “NO” .
  3. Iterar sobre los caracteres de la string S1 y actualizar s1hash .
  4. Repita los caracteres de la string S2 utilizando la técnica de ventana deslizante y actualice HashMap en consecuencia.
  5. Para cualquier substring de S2 de longitud igual a la longitud de S1, si se encuentra que ambos Hashmaps son iguales, imprima «SÍ» .
  6. 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)

Publicación traducida automáticamente

Artículo escrito por swagami6 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *