Overview
Course Introduction
Strings and Arrays
Reverse Words In A String
Rotate Array
Isomorphic Strings
Kth Largest Element In An Array
Matrix Problems
Set Matrix Zero
Spiral Matrix
Number Of Islands
Linked Lists
Implement A Stack Using An Array
Add Two Numbers As Reversed Linked Lists
Reverse A Linked List
Binary Trees
Inorder Traversal
Preorder Traversal
Postorder Traversal
Graph Problems
Clone a Graph: Build a Graph
Clone a Graph: Build a Queue
Clone a Graph: Breadth First Traversal (BFS)
Clone a Graph: Depth First Search (DFS)
Sorting & Time Complexities
Time Complexities (Bad)
Time Complexities (Good)
Bubble Sort
Selection Sort
Insertion Sort
Quicksort
Merge Sort
Time Complexity Of Different Sorting Algorithms
Dynamic Programming
Coin Change
Edit Distance
Distinct Subsequences
Bit Manipulation
Bitwise And Shift Operators
Single Number
Number Of 1 Bits
Sum of Two Integers
Maximum Sum Subarray
Reverse Bits
Bitwise And Of A Range
Combinations & Permutations
Permutations
Distinct Permutations Of A String
Letter Combinations Of A Phone Number
Factor Combinations
Math Problems
Reverse Integer
Palindrome Number
Excel Sheet Column Number
Isomorphic Strings
Given two strings, A and B, determine if they are isomorphic. Isomorphic means that for every character in string one, you can replace it with a matching character in string two, such that every occurrence of the same character gets replaced with the same character in the other string. Write a function called areIsomorphic that takes in string one and string two as the inputs and returns true if the strings are isomorphic and false if they are not.
Video Solution
Solution Walkthrough
1function areIsomorphic(str1, str2) {
2 if (str1.length !== str2.length) {
3 return false;
4 }
5
6 const map = new Map();
7
8 for (let i = 0; i < str1.length; i++) {
9 const char1 = str1[i];
10 const char2 = str2[i];
11
12 if (!map.has(char1)) {
13 map.set(char1, char2);
14 } else if (map.get(char1) !== char2) {
15 return false;
16 }
17 }
18
19 return true;
20}
21We start by checking if the lengths of both strings are equal. If not, we can return false because two strings of different lengths can never be isomorphic.
Next, we initialize a Map to store the character mappings from string one to string two. We will use the map to check if a character has already been mapped and to map new characters.
We then loop through each character in the strings and check if the character from string one has already been mapped. If not, we add it to the map with the corresponding character in string two. If the character from string one has already been mapped, we check if the corresponding character from string two matches the previous mapping. If not, we can immediately return false because the strings are not isomorphic.
Finally, if we loop through the entire strings and all character mappings match, we can return true because the strings are isomorphic.
Big O Complexity Analysis: The time complexity of this solution is O(n) because we are looping through each character in both strings once. The space complexity is also O(n) because we may need to store all characters in string one and their corresponding characters in string two in the map. However, in the worst case scenario where every character is unique, we would need to store all characters in both strings, leading to a space complexity of O(2n), which simplifies to O(n).
The use of a Map helps us achieve this time complexity as it allows constant time lookups and insertions.
Final Code Output:
1console.log(areIsomorphic("abc", "def")); // true
2console.log(areIsomorphic("aa", "ab")); // false
3console.log(areIsomorphic("aa", "bb")); // true
4