Dadas dos strings, la tarea es verificar si las frecuencias de un carácter (para cada carácter) en una string son múltiples o un factor en otra string. Si es así, envíe «SÍ», de lo contrario, envíe «NO».
Ejemplos:
Entrada: s1 = “aabccd”, s2 = “bbbaaaacc”
Salida: SI
La frecuencia de ‘a’ en s1 y s2 es 2 y 4 respectivamente, y 2 es un factor de 4
La frecuencia de ‘b’ en s1 y s2 es 1 y 3 respectivamente, y 1 es un factor de 3
La frecuencia de ‘c’ en s1 y s2 es la misma, por lo tanto, también satisface.
Las frecuencias de ‘d’ en s1 y s2 son 1 y 0 respectivamente, pero 0 es un múltiplo de cada número, por lo tanto satisfecho.
Por lo tanto, la respuesta SÍ.Entrada: s1 = “hhdwjwqq”, s2 = “qwjdddhhh”
Salida: NO
Acercarse:
- Almacene la frecuencia de los caracteres en s1 en el primer mapa STL.
- Almacene la frecuencia de los caracteres en s2 en el segundo mapa STL.
- Sea la frecuencia de un carácter en el primer mapa F1. Supongamos también que la frecuencia de este carácter en el segundo mapa es F2.
- Verifique F1%F2 y F2%F1 (operación de módulo). Si cualquiera de ellos es 0, entonces la condición se cumple.
- Compruébalo para todos los personajes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; // Function that checks if the frequency of character // are a factor or multiple of each other bool multipleOrFactor(string s1, string s2) { // map store frequency of each character map<char, int> m1, m2; for (int i = 0; i < s1.length(); i++) m1[s1[i]]++; for (int i = 0; i < s2.length(); i++) m2[s2[i]]++; map<char, int>::iterator it; for (it = m1.begin(); it != m1.end(); it++) { // if any frequency is 0, then continue // as condition is satisfied if (m2.find((*it).first) == m2.end()) continue; // if factor or multiple, then condition satisfied if (m2[(*it).first] % (*it).second == 0 || (*it).second % m2[(*it).first] == 0) continue; // if condition not satisfied else return false; } } // Driver code int main() { string s1 = "geeksforgeeks"; string s2 = "geeks"; multipleOrFactor(s1, s2) ? cout << "YES" : cout << "NO"; return 0; }
Java
// Java implementation of above approach import java.util.HashMap; class GFG { // Function that checks if the frequency of character // are a factor or multiple of each other public static boolean multipleOrFactor(String s1, String s2) { // map store frequency of each character HashMap<Character, Integer> m1 = new HashMap<>(); HashMap<Character, Integer> m2 = new HashMap<>(); for (int i = 0; i < s1.length(); i++) { if (m1.containsKey(s1.charAt(i))) { int x = m1.get(s1.charAt(i)); m1.put(s1.charAt(i), ++x); } else m1.put(s1.charAt(i), 1); } for (int i = 0; i < s2.length(); i++) { if (m2.containsKey(s2.charAt(i))) { int x = m2.get(s2.charAt(i)); m2.put(s2.charAt(i), ++x); } else m2.put(s2.charAt(i), 1); } for (HashMap.Entry<Character, Integer> entry : m1.entrySet()) { // if any frequency is 0, then continue // as condition is satisfied if (!m2.containsKey(entry.getKey())) continue; // if factor or multiple, then condition satisfied if (m2.get(entry.getKey()) != null && (m2.get(entry.getKey()) % entry.getValue() == 0 || entry.getValue() % m2.get(entry.getKey()) == 0)) continue; // if condition not satisfied else return false; } return true; } // Driver code public static void main(String[] args) { String s1 = "geeksforgeeks", s2 = "geeks"; if (multipleOrFactor(s1, s2)) System.out.println("Yes"); else System.out.println("No"); } } // This code is contributed by // sanjeev2552
Python3
# Python3 implementation of above approach from collections import defaultdict # Function that checks if the frequency of # character are a factor or multiple of each other def multipleOrFactor(s1, s2): # map store frequency of each character m1 = defaultdict(lambda:0) m2 = defaultdict(lambda:0) for i in range(0, len(s1)): m1[s1[i]] += 1 for i in range(0, len(s2)): m2[s2[i]] += 1 for it in m1: # if any frequency is 0, then continue # as condition is satisfied if it not in m2: continue # if factor or multiple, then condition satisfied if (m2[it] % m1[it] == 0 or m1[it] % m2[it] == 0): continue # if condition not satisfied else: return False return True # Driver code if __name__ == "__main__": s1 = "geeksforgeeks" s2 = "geeks" if multipleOrFactor(s1, s2): print("YES") else: print("NO") # This code is contributed by Rituraj Jain
C#
// C# implementation of the approach using System; using System.Collections.Generic; class GFG { // Function that checks if the // frequency of character are // a factor or multiple of each other public static Boolean multipleOrFactor(String s1, String s2) { // map store frequency of each character Dictionary<char, int> m1 = new Dictionary<char, int>(); Dictionary<char, int> m2 = new Dictionary<char, int>(); for (int i = 0; i < s1.Length; i++) { if (m1.ContainsKey(s1[i])) { var x = m1[s1[i]]; m1[s1[i]]= ++x; } else m1.Add(s1[i], 1); } for (int i = 0; i < s2.Length; i++) { if (m2.ContainsKey(s2[i])) { var x = m2[s2[i]]; m2[s2[i]]= ++x; } else m2.Add(s2[i], 1); } foreach(KeyValuePair<char, int> entry in m1) { // if any frequency is 0, then continue // as condition is satisfied if (!m2.ContainsKey(entry.Key)) continue; // if factor or multiple, then condition satisfied if (m2[entry.Key] != 0 && (m2[entry.Key] % entry.Value == 0 || entry.Value % m2[entry.Key] == 0)) continue; // if condition not satisfied else return false; } return true; } // Driver code public static void Main(String[] args) { String s1 = "geeksforgeeks", s2 = "geeks"; if (multipleOrFactor(s1, s2)) Console.WriteLine("Yes"); else Console.WriteLine("No"); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // JavaScript implementation of above approach // Function that checks if the frequency of character // are a factor or multiple of each other function multipleOrFactor(s1, s2){ // map store frequency of each character let m1 = new Map(); let m2 = new Map(); for (let i = 0; i < s1.length; i++){ if(m1[s1[i]]) m1[s1[i]]++; else m1[s1[i]] = 1 } for (let i = 0; i < s2.length; i++){ if(m2[s2[i]]) m2[s2[i]]++; else m2[s2[i]] = 1 } for (var it in m1) { // if any frequency is 0, then continue // as condition is satisfied if (!(m2[it])) continue; // if factor or multiple, then condition satisfied if (m2[it] % m1[it] == 0 || m1[it] % m2[it] == 0) continue; // if condition not satisfied else return false; } return true; } // Driver code let s1 = "geeksforgeeks"; let s2 = "geeks"; multipleOrFactor(s1, s2) ?document.write( "YES") : document.write("NO"); </script>
YES
Complejidad de tiempo: O((n+m)*log(n+m)), donde n es el tamaño de la string s1 y m es el tamaño de la string s2
Espacio auxiliar: O(n+m), donde n es el tamaño de la string s1 y m es el tamaño de la string s2
Publicación traducida automáticamente
Artículo escrito por Shashank_Sharma y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA