Dadas dos strings str y str1 , la tarea es verificar si una string se puede convertir en otra usando la siguiente operación:
- Convertir toda la presencia de un personaje por un personaje diferente.
Por ejemplo, si str = “abacd” y la operación es cambiar el carácter ‘a’ a ‘k’, entonces el resultado str = “kbkcd”
Ejemplos:
Entrada: str = “abbcaa”; str1 = “bccdbb”
Salida: Sí
Explicación: Las asignaciones de los caracteres son:
c –> d
b –> c
a –> b
Entrada: str = “abbc”; str1 = “bcca”
Salida: No
Explicación: El mapeo de caracteres es:
a –> b
b –> c
c –> a
Aquí, debido a la presencia de un ciclo, no se puede encontrar un orden específico.
Acercarse:
- De acuerdo con la operación dada, cada carácter único debe asignarse a un carácter único que puede ser igual o diferente.
- Esto se puede verificar fácilmente con un Hashmap .
- Sin embargo, esto falla en los casos en que hay un ciclo en el mapeo y no se puede determinar un orden específico.
- Un ejemplo de tal caso es el Ejemplo 2 anterior.
- Por lo tanto, para el mapeo, los caracteres primero y final se almacenan como bordes en un mapa hash.
- Para encontrar el ciclo con los bordes, estos bordes se asignan uno por uno a un padre y se verifica el ciclo utilizando Union and Find Algorithm .
A continuación se muestra la implementación del enfoque anterior.
CPP
// C++ implementation of the above approach. #include <bits/stdc++.h> using namespace std; int parent[26]; // Function for find // from Disjoint set algorithm int find(int x) { if (x != parent[x]) return parent[x] = find(parent[x]); return x; } // Function for the union // from Disjoint set algorithm void join(int x, int y) { int px = find(x); int pz = find(y); if (px != pz) { parent[pz] = px; } } // Function to check if one string // can be converted to another. bool convertible(string s1, string s2) { // All the characters are checked whether // it's either not replaced or replaced // by a similar character using a map. map<int, int> mp; for (int i = 0; i < s1.size(); i++) { if (mp.find(s1[i] - 'a') == mp.end()) { mp[s1[i] - 'a'] = s2[i] - 'a'; } else { if (mp[s1[i] - 'a'] != s2[i] - 'a') return false; } } // To check if there are cycles. // If yes, then they are not convertible. // Else, they are convertible. for (auto it : mp) { if (it.first == it.second) continue; else { if (find(it.first) == find(it.second)) return false; else join(it.first, it.second); } } return true; } // Function to initialize parent array // for union and find algorithm. void initialize() { for (int i = 0; i < 26; i++) { parent[i] = i; } } // Driver code int main() { // Your C++ Code string s1, s2; s1 = "abbcaa"; s2 = "bccdbb"; initialize(); if (convertible(s1, s2)) cout << "Yes" << endl; else cout << "No" << endl; return 0; }
Java
// Java implementation of the above approach. import java.util.*; class GFG { static int []parent = new int[26]; // Function for find // from Disjoint set algorithm static int find(int x) { if (x != parent[x]) return parent[x] = find(parent[x]); return x; } // Function for the union // from Disjoint set algorithm static void join(int x, int y) { int px = find(x); int pz = find(y); if (px != pz) { parent[pz] = px; } } // Function to check if one String // can be converted to another. static boolean convertible(String s1, String s2) { // All the characters are checked whether // it's either not replaced or replaced // by a similar character using a map. HashMap<Integer,Integer> mp = new HashMap<Integer,Integer>(); for (int i = 0; i < s1.length(); i++) { if (!mp.containsKey(s1.charAt(i) - 'a')) { mp.put(s1.charAt(i) - 'a', s2.charAt(i) - 'a'); } else { if (mp.get(s1.charAt(i) - 'a') != s2.charAt(i) - 'a') return false; } } // To check if there are cycles. // If yes, then they are not convertible. // Else, they are convertible. for (Map.Entry<Integer, Integer> it : mp.entrySet()) { if (it.getKey() == it.getValue()) continue; else { if (find(it.getKey()) == find(it.getValue())) return false; else join(it.getKey(), it.getValue()); } } return true; } // Function to initialize parent array // for union and find algorithm. static void initialize() { for (int i = 0; i < 26; i++) { parent[i] = i; } } // Driver code public static void main(String[] args) { String s1, s2; s1 = "abbcaa"; s2 = "bccdbb"; initialize(); if (convertible(s1, s2)) System.out.print("Yes" + "\n"); else System.out.print("No" + "\n"); } } // This code is contributed by 29AjayKumar
Python3
# Python3 implementation of the above approach. parent = [0] * 256 # Function for find # from Disjoset algorithm def find(x): if (x != parent[x]): parent[x] = find(parent[x]) return parent[x] return x # Function for the union # from Disjoset algorithm def join(x, y): px = find(x) pz = find(y) if (px != pz): parent[pz] = px # Function to check if one string # can be converted to another. def convertible(s1, s2): # All the characters are checked whether # it's either not replaced or replaced # by a similar character using a map. mp = dict() for i in range(len(s1)): if (s1[i] in mp): mp[s1[i]] = s2[i] else: if s1[i] in mp and mp[s1[i]] != s2[i]: return False # To check if there are cycles. # If yes, then they are not convertible. # Else, they are convertible. for it in mp: if (it == mp[it]): continue else : if (find(ord(it)) == find(ord(it))): return False else: join(ord(it), ord(it)) return True # Function to initialize parent array # for union and find algorithm. def initialize(): for i in range(256): parent[i] = i # Driver code s1 = "abbcaa" s2 = "bccdbb" initialize() if (convertible(s1, s2)): print("Yes") else: print("No") # This code is contributed by mohit kumar 29
C#
// C# implementation of the above approach. using System; using System.Collections.Generic; class GFG { static int []parent = new int[26]; // Function for find // from Disjoint set algorithm static int find(int x) { if (x != parent[x]) return parent[x] = find(parent[x]); return x; } // Function for the union // from Disjoint set algorithm static void join(int x, int y) { int px = find(x); int pz = find(y); if (px != pz) { parent[pz] = px; } } // Function to check if one String // can be converted to another. static bool convertible(String s1, String s2) { // All the characters are checked whether // it's either not replaced or replaced // by a similar character using a map. Dictionary<int,int> mp = new Dictionary<int,int>(); for (int i = 0; i < s1.Length; i++) { if (!mp.ContainsKey(s1[i] - 'a')) { mp.Add(s1[i] - 'a', s2[i] - 'a'); } else { if (mp[s1[i] - 'a'] != s2[i] - 'a') return false; } } // To check if there are cycles. // If yes, then they are not convertible. // Else, they are convertible. foreach(KeyValuePair<int, int> it in mp) { if (it.Key == it.Value) continue; else { if (find(it.Key) == find(it.Value)) return false; else join(it.Key, it.Value); } } return true; } // Function to initialize parent array // for union and find algorithm. static void initialize() { for (int i = 0; i < 26; i++) { parent[i] = i; } } // Driver code public static void Main(String[] args) { String s1, s2; s1 = "abbcaa"; s2 = "bccdbb"; initialize(); if (convertible(s1, s2)) Console.Write("Yes" + "\n"); else Console.Write("No" + "\n"); } } // This code is contributed by PrinciRaj1992
Javascript
<script> // JavaScript implementation of the above approach. var parent = new Array(26).fill(0); // Function for find // from Disjoint set algorithm function find(x) { if (x !== parent[x]) return (parent[x] = find(parent[x])); return x; } // Function for the union // from Disjoint set algorithm function join(x, y) { var px = find(x); var pz = find(y); if (px !== pz) { parent[pz] = px; } } // Function to check if one String // can be converted to another. function convertible(s1, s2) { // All the characters are checked whether // it's either not replaced or replaced // by a similar character using a map. var mp = {}; for (var i = 0; i < s1.length; i++) { if (!mp.hasOwnProperty(s1[i].charCodeAt(0) - "a".charCodeAt(0))) { mp[s1[i].charCodeAt(0) - "a".charCodeAt(0)] = s2[i].charCodeAt(0) - "a".charCodeAt(0); } else { if ( mp[s1[i].charCodeAt(0) - "a".charCodeAt(0)] !== s2[i].charCodeAt(0) - "a".charCodeAt(0) ) return false; } } // To check if there are cycles. // If yes, then they are not convertible. // Else, they are convertible. for (const [key, value] of Object.entries(mp)) { if (key === value) continue; else { if (find(key) == find(value)) return false; else join(key, value); } } return true; } // Function to initialize parent array // for union and find algorithm. function initialize() { for (var i = 0; i < 26; i++) { parent[i] = i; } } // Driver code var s1, s2; s1 = "abbcaa"; s2 = "bccdbb"; initialize(); if (convertible(s1, s2)) document.write("Yes" + "<br>"); else document.write("No" + "<br>"); </script>
Yes
Complejidad de tiempo: O(N * logN), donde N es la longitud de la string s1.
Espacio Auxiliar: O(N)
Publicación traducida automáticamente
Artículo escrito por internprep y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA