Dos strings str1 y str2 se denominan isomorfas si existe un mapeo uno a uno posible para cada carácter de str1 con cada carácter de str2. Y todas las apariciones de cada carácter en ‘str1’ se asignan al mismo carácter en ‘str2’.
Ejemplos:
C++
// C++ program to check if two strings are isomorphic #include <bits/stdc++.h> using namespace std; #define MAX_CHARS 256 // This function returns true if str1 and str2 are isomorphic bool areIsomorphic(string str1, string str2) { int m = str1.length(), n = str2.length(); // Length of both strings must be same for one to one // correspondence if (m != n) return false; // To mark visited characters in str2 bool marked[MAX_CHARS] = { false }; // To store mapping of every character from str1 to // that of str2. Initialize all entries of map as -1. int map[MAX_CHARS]; memset(map, -1, sizeof(map)); // Process all characters one by on for (int i = 0; i < n; i++) { // If current character of str1 is seen first // time in it. if (map[str1[i]] == -1) { // If current character of str2 is already // seen, one to one mapping not possible if (marked[str2[i]] == true) return false; // Mark current character of str2 as visited marked[str2[i]] = true; // Store mapping of current characters map[str1[i]] = str2[i]; } // If this is not first appearance of current // character in str1, then check if previous // appearance mapped to same character of str2 else if (map[str1[i]] != str2[i]) return false; } return true; } // Driver program int main() { cout << areIsomorphic("aab", "xxy") << endl; cout << areIsomorphic("aab", "xyz") << endl; return 0; }
Java
// Java program to check if two strings are isomorphic import java.io.*; import java.util.*; class Isomorphic { static int size = 256; // Function returns true if str1 and str2 are isomorphic static boolean areIsomorphic(String str1, String str2) { int m = str1.length(); int n = str2.length(); // Length of both strings must be same for one to // one correspondence if (m != n) return false; // To mark visited characters in str2 Boolean[] marked = new Boolean[size]; Arrays.fill(marked, Boolean.FALSE); // To store mapping of every character from str1 to // that of str2. Initialize all entries of map as // -1. int[] map = new int[size]; Arrays.fill(map, -1); // Process all characters one by on for (int i = 0; i < n; i++) { // If current character of str1 is seen first // time in it. if (map[str1.charAt(i)] == -1) { // If current character of str2 is already // seen, one to one mapping not possible if (marked[str2.charAt(i)] == true) return false; // Mark current character of str2 as visited marked[str2.charAt(i)] = true; // Store mapping of current characters map[str1.charAt(i)] = str2.charAt(i); } // If this is not first appearance of current // character in str1, then check if previous // appearance mapped to same character of str2 else if (map[str1.charAt(i)] != str2.charAt(i)) return false; } return true; } // driver program public static void main(String[] args) { boolean res = areIsomorphic("aab", "xxy"); System.out.println(res); res = areIsomorphic("aab", "xyz"); System.out.println(res); } }
Python
# Python program to check if two strings are isomorphic MAX_CHARS = 256 # This function returns true if str1 and str2 are isomorphic def areIsomorphic(string1, string2): m = len(string1) n = len(string2) # Length of both strings must be same for one to one # correspondence if m != n: return False # To mark visited characters in str2 marked = [False] * MAX_CHARS # To store mapping of every character from str1 to # that of str2. Initialize all entries of map as -1 map = [-1] * MAX_CHARS # Process all characters one by one for i in xrange(n): # if current character of str1 is seen first # time in it. if map[ord(string1[i])] == -1: # if current character of st2 is already # seen, one to one mapping not possible if marked[ord(string2[i])] == True: return False # Mark current character of str2 as visited marked[ord(string2[i])] = True # Store mapping of current characters map[ord(string1[i])] = string2[i] # If this is not first appearance of current # character in str1, then check if previous # appearance mapped to same character of str2 elif map[ord(string1[i])] != string2[i]: return False return True # Driver program print areIsomorphic("aab", "xxy") print areIsomorphic("aab", "xyz") # This code is contributed by Bhavya Jain
C#
// C# program to check if two // strings are isomorphic using System; class GFG { static int size = 256; // Function returns true if str1 // and str2 are isomorphic static bool areIsomorphic(String str1, String str2) { int m = str1.Length; int n = str2.Length; // Length of both strings must be same // for one to one correspondence if (m != n) return false; // To mark visited characters in str2 bool[] marked = new bool[size]; for (int i = 0; i < size; i++) marked[i] = false; // To store mapping of every character // from str1 to that of str2 and // Initialize all entries of map as -1. int[] map = new int[size]; for (int i = 0; i < size; i++) map[i] = -1; // Process all characters one by on for (int i = 0; i < n; i++) { // If current character of str1 is // seen first time in it. if (map[str1[i]] == -1) { // If current character of str2 // is already seen, one to // one mapping not possible if (marked[str2[i]] == true) return false; // Mark current character of // str2 as visited marked[str2[i]] = true; // Store mapping of current characters map[str1[i]] = str2[i]; } // If this is not first appearance of current // character in str1, then check if previous // appearance mapped to same character of str2 else if (map[str1[i]] != str2[i]) return false; } return true; } // Driver code public static void Main() { bool res = areIsomorphic("aab", "xxy"); Console.WriteLine(res); res = areIsomorphic("aab", "xyz"); Console.WriteLine(res); } } // This code is contributed by Sam007.
Javascript
<script> // Javascript program to check if two // strings are isomorphic let size = 256; // Function returns true if str1 // and str2 are isomorphic function areIsomorphic(str1, str2) { let m = str1.length; let n = str2.length; // Length of both strings must be same // for one to one correspondence if(m != n) return false; // To mark visited characters in str2 let marked = new Array(size); for(let i = 0; i < size; i++) marked[i]= false; // To store mapping of every character // from str1 to that of str2 and // Initialize all entries of map as -1. let map = new Array(size); map.fill(0); for(let i = 0; i < size; i++) map[i]= -1; // Process all characters one by on for (let i = 0; i < n; i++) { // If current character of str1 is // seen first time in it. if (map[str1[i].charCodeAt()] == -1) { // If current character of str2 // is already seen, one to // one mapping not possible if (marked[str2[i].charCodeAt()] == true) return false; // Mark current character of // str2 as visited marked[str2[i].charCodeAt()] = true; // Store mapping of current characters map[str1[i].charCodeAt()] = str2[i].charCodeAt(); } // If this is not first appearance of current // character in str1, then check if previous // appearance mapped to same character of str2 else if (map[str1[i].charCodeAt()] != str2[i].charCodeAt()) return 0; } return 1; } let res = areIsomorphic("aab", "xxy"); document.write(res + "</br>"); res = areIsomorphic("aab", "xyz"); document.write(res); // This code is contributed by decode2207. </script>
C++
// C++ program for the above approach #include <bits/stdc++.h> using namespace std; #define MAX_CHARS 26 // This function returns true if // str1 and str2 are isomorphic bool areIsomorphic(string str1, string str2) { int n = str1.length(), m = str2.length(); // Length of both strings must be // same for one to one // correspondence if (n != m) return false; // For counting the previous appearances of character in // both the strings int count[MAX_CHARS] = { 0 }; int dcount[MAX_CHARS] = { 0 }; // Process all characters one by one for (int i = 0; i < n; i++) { count[str1[i] - 'a']++; dcount[str2[i] - 'a']++; } // For string to be isomorphic the previous counts // of appearances of // current character in both string must be same if // it is not same we return false. //before it was not working for the test case mentioned below(wrong output) // str1 = "aba" , str2 = "xyy" for(int i= 0; i < n; i++) { if (count[str1[i] - 'a'] != dcount[str2[i] - 'a']) { return false; } } return true; } // Driver Code int main() { cout << areIsomorphic("aab", "xxy") << endl; cout << areIsomorphic("aba", "xyy") << endl; return 0; }
Java
// Java program for the above approach import java.io.*; class GFG { static final int CHAR = 26; // This function returns true if // str1 and str2 are isomorphic static boolean isoMorphic(String str1, String str2) { int n = str1.length(); int m = str2.length(); // Length of both strings must be // same for one to one // correspondence if (n != m) return false; // For counting the previous appearances // of character in both the strings int[] countChars1 = new int[CHAR]; int[] countChars2 = new int[CHAR]; // Process all characters one by one for (int i = 0; i < n; i++) { countChars1[str1.charAt(i) - 'a']++; countChars2[str2.charAt(i) - 'a']++; } // For string to be isomorphic the // previous counts of appearances of // current character in both string // must be same if it is not same we // return false. //before it was not working for the test case mentioned below(wrong output) // str1 = "aba" , str2 = "xyy" for(int i= 0; i < n; i++) { if (countChars1[str1.charAt(i) - 'a'] != countChars2[str2.charAt(i) - 'a']) { return false; } } return true; } // Driver Code public static void main(String[] args) { System.out.println(isoMorphic("aab", "xxy") ? 1 : 0); System.out.println(isoMorphic("aba", "xyy") ? 1 : 0); } } // This code is contributed by rohansharma1808
Python3
# Python3 program for the above approach CHAR = 26 # This function returns true if # str1 and str2 are isomorphic def isoMorphic(str1, str2): n = len(str1) m = len(str2) # Length of both strings must be # same for one to one correspondence if n != m: return False # for counting the previous appearances of character # in both the strings countChars1 = [0] * CHAR countChars2 = [0] * CHAR # Process all characters one by one for i in range(n): countChars1[ord(str1[i]) - ord('a')] += 1 countChars2[ord(str2[i]) - ord('a')] += 1 # For string to be isomorphice the # previous counts of appearances of # current character in both string # must be same if it is not same # we return false for i in range(n): if countChars1[ord(str1[i]) - ord('a')] != countChars2[ord(str2[i]) - ord('a')]: return False return True # Driver Code print(int(isoMorphic("aab", "xxy"))) print(int(isoMorphic("aab", "xyz"))) # This code is contributed by phasing17
C#
// C# program for the above approach using System; class GFG { static int CHAR = 26; // This function returns true if // str1 and str2 are isomorphic static bool isoMorphic(string str1, string str2) { int n = str1.Length; int m = str2.Length; // Length of both strings must be // same for one to one // correspondence if (n != m) return false; // For counting the previous appearances // of character in both the strings int[] countChars1 = new int[CHAR]; int[] countChars2 = new int[CHAR]; // Process all characters one by one for (int i = 0; i < n; i++) { countChars1[str1[i] - 'a']++; countChars2[str2[i] - 'a']++; } // For string to be isomorphic the // previous counts of appearances of // current character in both string // must be same if it is not same we // return false. //before it was not working for the test case mentioned below(wrong output) // str1 = "aba" , str2 = "xyy" for (int i = 0; i < n; i++) { if (countChars1[str1[i] - 'a'] != countChars2[str2[i] - 'a']) { return false; } } return true; } // Driver Code public static void Main(string[] args) { Console.WriteLine(isoMorphic("aab", "xxy") ? 1 : 0); Console.WriteLine(isoMorphic("aab", "xyz") ? 1 : 0); } } // This code is contributed by ukasp.
Javascript
<script> // Javascript program for the above approach let CHAR = 26; // This function returns true if // str1 and str2 are isomorphic function isoMorphic(str1, str2) { let n = str1.length; let m = str2.length; // Length of both strings must be // same for one to one // correspondence if (n != m) return false; // For counting the previous appearances // of character in both the strings let countChars1 = new Array(CHAR); countChars1.fill(0); let countChars2 = new Array(CHAR); countChars2.fill(0); // Process all characters one by one for(let i = 0; i < n; i++) { countChars1[str1[i].charCodeAt()-'a']++; countChars2[str2[i].charCodeAt()-'a']++; } // For string to be isomorphic the // previous counts of appearances of // current character in both string // must be same if it is not same we // return false. for(let i = 0; i < n; i++) { if (countChars1[str1[i].charCodeAt()-'a'] != countChars2[str2[i].charCodeAt()-'a']) { return false; } } return true; } document.write(isoMorphic("aab", "xxy") ? 1 + "</br>" : 0 + "</br>"); document.write(isoMorphic("aab", "xyz") ? 1 : 0); </script>
C#
// C# program to check if two strings // areIsIsomorphic using System; using System.Collections.Generic; public class GFG { static bool areIsomorphic(char[] str1, char[] str2) { Dictionary<char, char> charCount = new Dictionary<char, char>(); char c = 'a'; for (int i = 0; i < str1.Length; i++) { if (charCount.ContainsKey(str1[i]) && charCount.TryGetValue(str1[i], out c)) { if (c != str2[i]) return false; } else if (!charCount.ContainsValue(str2[i])) { charCount.Add(str1[i], str2[i]); } else { return false; } } return true; } /* Driver code*/ public static void Main() { string str1 = "aac"; string str2 = "xxy"; // Function Call if (str1.Length == str2.Length && areIsomorphic(str1.ToCharArray(), str2.ToCharArray())) Console.WriteLine(1); else Console.WriteLine(0); Console.ReadLine(); } }
Java
// Java program to check if two strings // areIsIsomorphic import java.util.*; public class GFG { static boolean areIsomorphic(char[] str1, char[] str2) { HashMap<Character, Character> charCount = new HashMap(); char c = 'a'; for (int i = 0; i < str1.length; i++) { if (charCount.containsKey(str1[i])) { c = charCount.get(str1[i]); if (c != str2[i]) return false; } else if (!charCount.containsValue(str2[i])) { charCount.put(str1[i], str2[i]); } else { return false; } } return true; } /* Driver code*/ public static void main(String[] args) { String str1 = "aac"; String str2 = "xxy"; // Function Call if (str1.length() == str2.length() && areIsomorphic(str1.toCharArray(), str2.toCharArray())) System.out.println(1); else System.out.println(0); } } // This code is contributed by phasing17
Python3
# Python3 program to check if two strings are IsIsomorphic #this function returns true if str1 #and str2 are isomorphic def areIsomorphic(str1, str2): #initializing a dictionary #to store letters from str1 and str2 #as key value pairs charCount = dict() #initially setting c to "a" c = "a" #iterating over str1 and str2 for i in range(len(str1)): #if str1[i] is a key in charCount if str1[i] in charCount: c = charCount[str1[i]] if c != str2[i]: return False #if str2[i] is not a value in charCount elif str2[i] not in charCount.values(): charCount[str1[i]] = str2[i] else: return False return True #Driver Code str1 = "aac" str2 = "xxy" #Function Call if (len(str1) == len(str2) and areIsomorphic(str1, str2)): print(1) else: print(0) #this code is contributed by phasing17
Javascript
<script> // JavaScript program to check if two strings are IsIsomorphic // this function returns true if str1 // and str2 are isomorphic function areIsomorphic(str1, str2) { // initializing an object // to store letters from str1 and str2 // as key value pairs var charCount = {}; // initially setting c to "a" var c = "a"; // iterating over str1 and str2 for (var i = 0; i < str1.length; i++) { // if str1[i] is a key in charCount if (charCount.hasOwnProperty(str1[i])) { c = charCount[str1[i]]; if (c != str2[i]) return false; } // if str2[i] is not a value in charCount else if (!Object.values(charCount).includes(str2[i])) { charCount[str1[i]] = str2[i]; } else return false; } return true; } // Driver Code var str1 = "aac"; var str2 = "xxy"; // Function Call if (str1.length == str2.length && areIsomorphic(str1, str2)) document.write(1); else document.write(0); // This code is contributed by phasing17. </script>
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA