El número de strings en dos arrays satisface las condiciones dadas

Posted on by Rudeus Greyrat

Dadas dos arrays de strings arr1[] y arr2[] . Para cada string en arr2[] (digamos str2 ), la tarea es contar la string de números en arr1[] (digamos str1 ) que satisfagan las siguientes condiciones:

  • Los primeros caracteres de str1 y str2 deben ser iguales.
  • La string str2 debe contener cada carácter de la string str1 .

Ejemplos:

Entrada: arr1[] = {“aaaa”, “asas”, “capaz”, “habilidad”, “actt”, “actor”, “acceso”}, arr2[] = {“aboveyz”, “abrodyz”, “ absoluto”, “absoryz”, “actresz”, “gaswxyz”} 
Salida: 
1 
1 
3 
2 
4 
0 
Explicación: 
La siguiente es la string en arr1[] que sigue la condición dada: 
1 palabra válida para “aboveyz”: “aaaa ”. 
1 palabra válida para “abrodyz”: “aaaa”. 
3 palabras válidas para “absoluto”: “aaaa”, “asas”, “able”. 
2 palabras válidas para “absoryz” : “aaaa”, “asas”. 
4 palabras válidas para “actresz” : “aaaa”, “asas”, “actt”, “access”. 
No hay palabras válidas para “gaswxyz” porque ninguna de las palabras de la lista contiene la letra ‘g’.

Entrada: arr1[] = {“abbg”, “able”, “absolute”, “abil”, “actresz”, “gaswxyz”}, arr2[] = {“abbgaaa”, “asas”, “able”, “ habilidad”} 
Salida: 
1 
0 
1 
1

Enfoque: Este problema se puede resolver utilizando el concepto de Bitmasking . A continuación se muestran los pasos:

  • Convierta cada string de la array arr1[] en su máscara de bits correspondiente, como se muestra a continuación:
For string str = "abcd"
the corresponding bitmask conversion is:
characters | value 
    a          0
    b          1
    c          2
    d          3
As per the above characters value, the number is:
value = 20 + 21 + 23 + 24
value = 15.
so the string "abcd" represented as 15.
  • Nota: Al aplicar una máscara de bits a cada string, si la frecuencia de los caracteres es superior a 1, incluya los caracteres correspondientes solo una vez.
  • Almacene la frecuencia de cada string en un mapa_desordenado .
  • De manera similar, convierta cada string en arr2[] a la máscara de bits correspondiente y haga lo siguiente:
    • En lugar de calcular todas las palabras posibles correspondientes a arr1[] , use la operación de bits para encontrar la siguiente máscara de bits válida usando temp = (temp – 1)&val .
    • Produce el siguiente patrón de máscara de bits, reduciendo un carácter a la vez mediante la producción de todas las combinaciones posibles.
  • Para cada permutación válida, verifique si valida las dos condiciones dadas y agrega la frecuencia correspondiente a la string actual almacenada en un mapa_desordenado al 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;
 
void findNumOfValidWords(vector<string>& w,
                         vector<string>& p)
{
    // To store the frequency of string
    // after bitmasking
    unordered_map<int, int> m;
 
    // To store result for each string
    // in arr2[]
    vector<int> res;
 
    // Traverse the arr1[] and bitmask each
    // string in it
    for (string& s : w) {
 
        int val = 0;
 
        // Bitmasking for each string s
        for (char c : s) {
            val = val | (1 << (c - 'a'));
        }
 
        // Update the frequency of string
        // with it's bitmasking value
        m[val]++;
    }
 
    // Traverse the arr2[]
    for (string& s : p) {
        int val = 0;
 
        // Bitmasking for each string s
        for (char c : s) {
            val = val | (1 << (c - 'a'));
        }
 
        int temp = val;
        int first = s[0] - 'a';
        int count = 0;
 
        while (temp != 0) {
 
            // Check if temp is present
            // in an unordered_map or not
            if (((temp >> first) & 1) == 1) {
                if (m.find(temp) != m.end()) {
                    count += m[temp];
                }
            }
 
            // Check for next set bit
            temp = (temp - 1) & val;
        }
 
        // Push the count for current
        // string in resultant array
        res.push_back(count);
    }
 
    // Print the count for each string
    for (auto& it : res) {
        cout << it << '\n';
    }
}
 
// Driver Code
int main()
{
    vector<string> arr1;
    arr1 = { "aaaa", "asas", "able",
             "ability", "actt",
             "actor", "access" };
 
    vector<string> arr2;
    arr2 = { "aboveyz", "abrodyz",
             "absolute", "absoryz",
             "actresz", "gaswxyz" };
 
    // Function call
    findNumOfValidWords(arr1, arr2);
    return 0;
}

Java

// Java program for
// the above approach
import java.util.*;
class GFG{
 
static void findNumOfValidWords(Vector<String> w,
                                Vector<String> p)
{
  // To store the frequency of String
  // after bitmasking
  HashMap<Integer,
          Integer> m = new HashMap<>();
 
  // To store result for
  // each string in arr2[]
  Vector<Integer> res = new Vector<>();
 
  // Traverse the arr1[] and
  // bitmask each string in it
  for (String s : w)
  {
    int val = 0;
 
    // Bitmasking for each String s
    for (char c : s.toCharArray())
    {
      val = val | (1 << (c - 'a'));
    }
 
    // Update the frequency of String
    // with it's bitmasking value
    if(m.containsKey(val))
      m.put(val, m.get(val) + 1);
    else
      m.put(val, 1);
  }
 
  // Traverse the arr2[]
  for (String s : p)
  {
    int val = 0;
 
    // Bitmasking for each String s
    for (char c : s.toCharArray())
    {
      val = val | (1 << (c - 'a'));
    }
 
    int temp = val;
    int first = s.charAt(0) - 'a';
    int count = 0;
 
    while (temp != 0)
    {
      // Check if temp is present
      // in an unordered_map or not
      if (((temp >> first) & 1) == 1)
      {
        if (m.containsKey(temp))
        {
          count += m.get(temp);
        }
      }
 
      // Check for next set bit
      temp = (temp - 1) & val;
    }
 
    // Push the count for current
    // String in resultant array
    res.add(count);
  }
 
  // Print the count for each String
  for (int it : res)
  {
    System.out.println(it);
  }
}
 
// Driver Code
public static void main(String[] args)
{
  Vector<String> arr1 = new Vector<>();
  arr1.add("aaaa"); arr1.add("asas");
  arr1.add("able"); arr1.add("ability");
  arr1.add("actt"); arr1.add("actor");
  arr1.add("access");
 
  Vector<String> arr2 = new Vector<>();
  arr2.add("aboveyz"); arr2.add("abrodyz");
  arr2.add("absolute"); arr2.add("absoryz");
  arr2.add("actresz"); arr2.add("gaswxyz");
 
  // Function call
  findNumOfValidWords(arr1, arr2);
}
}
 
// This code is contributed by Princi Singh

Python3

# Python3 program for the above approach
from collections import defaultdict
 
def findNumOfValidWords(w, p):
 
    # To store the frequency of string
    # after bitmasking
    m = defaultdict(int)
 
    # To store result for each string
    # in arr2[]
    res = []
 
    # Traverse the arr1[] and bitmask each
    # string in it
    for s in w:
        val = 0
 
        # Bitmasking for each string s
        for c in s:
            val = val | (1 << (ord(c) - ord('a')))
 
        # Update the frequency of string
        # with it's bitmasking value
        m[val] += 1
 
    # Traverse the arr2[]
    for s in p:
        val = 0
 
        # Bitmasking for each string s
        for c in s:
            val = val | (1 << (ord(c) - ord('a')))
 
        temp = val
        first = ord(s[0]) - ord('a')
        count = 0
         
        while (temp != 0):
 
            # Check if temp is present
            # in an unordered_map or not
            if (((temp >> first) & 1) == 1):
                if (temp in m):
                    count += m[temp]
 
            # Check for next set bit
            temp = (temp - 1) & val
 
        # Push the count for current
        # string in resultant array
        res.append(count)
     
    # Print the count for each string
    for it in res:
        print(it)
 
# Driver Code
if __name__ == "__main__":
 
    arr1 = [ "aaaa", "asas", "able",
             "ability", "actt",
             "actor", "access" ]
 
    arr2 = [ "aboveyz", "abrodyz",
             "absolute", "absoryz",
             "actresz", "gaswxyz" ]
 
    # Function call
    findNumOfValidWords(arr1, arr2)
 
# This code is contributed by chitranayal

C#

// C# program for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
 
static void findNumOfValidWords(List<String> w,
                                List<String> p)
{
  // To store the frequency of String
  // after bitmasking
  Dictionary<int,
             int> m = new Dictionary<int,
                                     int>();
   
  // To store result for
  // each string in arr2[]
  List<int> res = new List<int>();
 
  // Traverse the arr1[] and
  // bitmask each string in it
  foreach (String s in w)
  {
    int val = 0;
 
    // Bitmasking for each String s
    foreach (char c in s.ToCharArray())
    {
      val = val | (1 << (c - 'a'));
    }
 
    // Update the frequency of String
    // with it's bitmasking value
    if(m.ContainsKey(val))
      m[val] = m[val] + 1;
    else
      m.Add(val, 1);
  }
 
  // Traverse the arr2[]
  foreach (String s in p)
  {
    int val = 0;
 
    // Bitmasking for each String s
    foreach (char c in s.ToCharArray())
    {
      val = val | (1 << (c - 'a'));
    }
 
    int temp = val;
    int first = s[0] - 'a';
    int count = 0;
 
    while (temp != 0)
    {
      // Check if temp is present
      // in an unordered_map or not
      if (((temp >> first) & 1) == 1)
      {
        if (m.ContainsKey(temp))
        {
          count += m[temp];
        }
      }
 
      // Check for next set bit
      temp = (temp - 1) & val;
    }
 
    // Push the count for current
    // String in resultant array
    res.Add(count);
  }
 
  // Print the count
  // for each String
  foreach (int it in res)
  {
    Console.WriteLine(it);
  }
}
 
// Driver Code
public static void Main(String[] args)
{
  List<String> arr1 = new List<String>();
  arr1.Add("aaaa"); arr1.Add("asas");
  arr1.Add("able"); arr1.Add("ability");
  arr1.Add("actt"); arr1.Add("actor");
  arr1.Add("access");
 
  List<String> arr2 = new List<String>();
  arr2.Add("aboveyz"); arr2.Add("abrodyz");
  arr2.Add("absolute"); arr2.Add("absoryz");
  arr2.Add("actresz"); arr2.Add("gaswxyz");
 
  // Function call
  findNumOfValidWords(arr1, arr2);
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
 
// Javascript program for the above approach
 
function findNumOfValidWords(w, p)
{
    // To store the frequency of string
    // after bitmasking
    var m = new Map();
 
    // To store result for each string
    // in arr2[]
    var res = [];
 
    // Traverse the arr1[] and bitmask each
    // string in it
    w.forEach(s => {
        var val = 0;
 
        // Bitmasking for each string s
        s.split('').forEach(c => {
            val = val | (1 << (c.charCodeAt(0) - 'a'.charCodeAt(0)));
        });
 
        // Update the frequency of string
        // with it's bitmasking value
        if(m.has(val))
            m.set(val, m.get(val)+1)
        else
            m.set(val, 1)
    });
 
    // Traverse the arr2[]
    p.forEach(s => {
        var val = 0;
        s.split('').forEach(c => {
            val = val | (1 << (c.charCodeAt(0) - 'a'.charCodeAt(0)));
        });
 
        var temp = val;
        var first = s[0].charCodeAt(0) - 'a'.charCodeAt(0);
        var count = 0;
 
        while (temp != 0) {
 
            // Check if temp is present
            // in an unordered_map or not
            if (((temp >> first) & 1) == 1) {
                if (m.has(temp)) {
                    count += m.get(temp);
                }
            }
 
            // Check for next set bit
            temp = (temp - 1) & val;
        }
 
        // Push the count for current
        // string in resultant array
        res.push(count);
    });
 
    // Print the count for each string
    res.forEach(it => {
         
        document.write( it + "<br>");
    });
}
 
// Driver Code
var arr1 = ["aaaa", "asas", "able",
         "ability", "actt",
         "actor", "access" ];
 
var arr2 = [ "aboveyz", "abrodyz",
         "absolute", "absoryz",
         "actresz", "gaswxyz" ];
// Function call
findNumOfValidWords(arr1, arr2);
 
</script>
Producción: 

1
1
3
2
4
0

 

Complejidad temporal: O(N) 
Complejidad espacial: O(N) 

Publicación traducida automáticamente

Artículo escrito por coder001 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 *