Isomorphic Strings solution and explanation
Google
9 more videos on this problem
Isomorphic Strings - Leetcode 205 - PythonNeetCode · 10:07 · 113K views
Isomorphic Strings (LeetCode 205) | Full solution using a HashMap | Easy to understandNikhil Lohia · 15:27 · 88K views
Isomorphic Strings | LeetCode problem 205Technosage · 7:09 · 64K views
205. Isomorphic Strings | Hash Map | StringsAryan Mittal · 15:35 · 8K views
Isomorphic Strings - LeetCode #205 - Python, JavaScript, Java, C++CodingNinja · 17:50 · 5K views
[Coding Interview] [LeetCode Tutorial] LeetCode 205 Isomorphic StringsZiCode · 14:03 · 5K views
Isomorphic Strings #leetcode #topinterview150Deepti Talesra · 6:47 · 2K views
Leetcode | 205. Isomorphic Strings | Easy | Java SolutionDeveloper Docs · 7:49 · 1K views
LeetCode 205 - Isomorphic Strings | Java Solution [EASY]Code with Carter · 11:06 · 1K views
205. Isomorphic Strings || HashMap || leetCode 205 || Easy || javaLIFE CODING WITH JAVA · 20:43 · 256 views
The problem
Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character, but a character may map to itself.
Example 1:
Input: s = "egg", t = "add"
Output: true
Explanation:
The strings s and t can be made identical by:
- Mapping
'e'to'a'. - Mapping
'g'to'd'.
Example 2:
Input: s = "foo", t = "bar"
Output: false
Explanation:
The strings s and t can not be made identical as 'o' needs to be mapped to both 'a' and 'r'.
Example 3:
Input: s = "paper", t = "title"
Output: true
Constraints:
1 <= s.length <= 5 * 104t.length == s.lengthsandtconsist of any valid ascii character.
Approach overview
Problem Overview: Given two strings s and t, determine whether they are isomorphic. Two strings are isomorphic if characters in s can be replaced to get t while preserving order. Each character must map to exactly one character, and no two characters can map to the same target character.
Approach 1: One-to-One Character Mapping (O(n) time, O(k) space)
This approach enforces a strict one-to-one mapping between characters in the two strings using hash tables. Iterate through both strings simultaneously and maintain a mapping from s[i] to t[i]. If the character in s was seen before, verify that it maps to the same character in t. To prevent two characters mapping to the same target, maintain a second set or reverse map to track already-mapped characters.
The key insight is that isomorphic strings behave like a bijection: every source character must consistently map to one target character. Hash lookups make each validation constant time, so the entire scan runs in O(n). Space complexity is O(k), where k is the number of unique characters (bounded by the character set). This method relies heavily on a Hash Table for constant-time mapping and works well for general String problems involving character relationships.
Approach 2: Unique Pattern Generation (O(n) time, O(n) space)
Instead of directly mapping characters, convert each string into a structural pattern that represents how characters appear. Traverse the string and assign each new character an increasing index based on its first occurrence. For example, the string egg becomes the pattern [0,1,1], and add produces the same pattern.
Generate this pattern for both strings and compare the resulting sequences. If the patterns match, the strings are isomorphic. This works because the pattern encodes the structure of character repetition and ordering. Pattern generation uses a hash map to track first occurrences and builds an array of indices, giving O(n) time and O(n) space.
This method is conceptually clean and helpful when reasoning about structural equivalence between strings. It also generalizes well to problems where you compare patterns rather than raw characters.
Recommended for interviews: The one-to-one character mapping approach is what interviewers typically expect. It directly models the bijection requirement and demonstrates comfort with hash table lookups and constraint validation during iteration. Mentioning the pattern-generation method shows deeper understanding, but the mapping solution is simpler, uses less memory, and is the most common production implementation.
Approach 1: One-to-One Character Mapping
This approach involves using two hash maps (or dictionaries) to track the character mappings from string s to string t and vice versa. We iterate over the characters of both strings and update the mappings. If at any point the expected character mapping does not match, we conclude that the strings are not isomorphic.
def isIsomorphic(s, t):
map_s, map_t = {}, {}
for cs, ct in zip(s, t):
if map_s.get(cs, ct) != ct or map_t.get(ct, cs) != cs:
return False
map_s[cs] = ct
map_t[ct] = cs
return Trueimport java.util.HashMap;
public class IsomorphicStrings {
public boolean isIsomorphic(String s, String t) {
HashMap<Character, Character> map_s = new HashMap<>();
HashMap<Character, Character> map_t = new HashMap<>();
for (int i = 0; i < s.length(); ++i) {
char sc = s.charAt(i);
char tc = t.charAt(i);
if (map_s.containsKey(sc) && map_s.get(sc) != tc ||
map_t.containsKey(tc) && map_t.get(tc) != sc)
return false;
map_s.put(sc, tc);
map_t.put(tc, sc);
}
return true;
}
}#include <unordered_map>
#include <string>
using namespace std;
bool isIsomorphic(string s, string t) {
unordered_map<char, char> map_s, map_t;
for (int i = 0; i < s.length(); ++i) {
if (map_s.count(s[i]) != map_t.count(t[i])) || (map_s[s[i]] != map_t[t[i]]) {
return false;
}
map_s[s[i]] = t[i];
map_t[t[i]] = s[i];
}
return true;
}function isIsomorphic(s, t) {
let map_s = {}, map_t = {};
for (let i = 0; i < s.length; i++) {
let cs = s[i], ct = t[i];
if ((cs in map_s && map_s[cs] !== ct) || (ct in map_t && map_t[ct] !== cs)) {
return false;
}
map_s[cs] = ct;
map_t[ct] = cs;
}
return true;
}#include <stdbool.h>
#include <string.h>
bool isIsomorphic(char * s, char * t) {
int map_s[256] = {0};
int map_t[256] = {0};
int len = strlen(s);
for (int i = 0; i < len; i++) {
if (map_s[s[i]] != map_t[t[i]]) {
return false;
}
map_s[s[i]] = map_t[t[i]] = i + 1;
}
return true;
}using System;
using System.Collections.Generic;
public class Solution {
public bool IsIsomorphic(string s, string t) {
Dictionary<char, char> map_s = new Dictionary<char, char>();
Dictionary<char, char> map_t = new Dictionary<char, char>();
for (int i = 0; i < s.Length; i++) {
if ((map_s.ContainsKey(s[i]) && map_s[s[i]] != t[i]) ||
(map_t.ContainsKey(t[i]) && map_t[t[i]] != s[i]))
return false;
map_s[s[i]] = t[i];
map_t[t[i]] = s[i];
}
return true;
}
}We create two dictionaries to check and store character mappings between strings s and t. During each comparison, consistency is checked, ensuring a valid bidirectional mapping is followed.
Time Complexity: O(n), where n is the number of characters in the strings.
Space Complexity: O(1), as the dictionaries at most grow to the size of the character set.
Approach 2: Unique Pattern Generation
Generate a unique pattern for each string by numbering the characters according to their first appearance. Compare character patterns of the two strings. If the patterns match, the strings are isomorphic.
def generatePattern(s):
map = {}
pattern = []
engine = 1
for c in s:
if c not in map:
map[c] = engine
engine += 1
pattern.append(map[c])
return pattern
def isIsomorphic(s, t):
return generatePattern(s) == generatePattern(t)import java.util.*;
public class IsomorphicStrings {
private List<Integer> generatePattern(String s) {
Map<Character, Integer> map = new HashMap<>();
List<Integer> pattern = new ArrayList<>();
int engine = 1;
for (char c : s.toCharArray()) {
if (!map.containsKey(c)) {
map.put(c, engine++);
}
pattern.add(map.get(c));
}
return pattern;
}
public boolean isIsomorphic(String s, String t) {
return generatePattern(s).equals(generatePattern(t));
}
}#include <vector>
#include <string>
using namespace std;
vector<int> generatePattern(const string &s) {
vector<int> pattern(s.size());
unordered_map<char, int> map;
int engine = 1;
for (int i = 0; i < s.size(); ++i) {
if (map.find(s[i]) == map.end()) {
map[s[i]] = engine++;
}
pattern[i] = map[s[i]];
}
return pattern;
}
bool isIsomorphic(string s, string t) {
return generatePattern(s) == generatePattern(t);
}function generatePattern(s) {
let map = {}, pattern = [];
let engine = 1;
for (let i = 0; i < s.length; ++i) {
if (!map[s[i]]) {
map[s[i]] = engine++;
}
pattern.push(map[s[i]]);
}
return pattern;
}
function isIsomorphic(s, t) {
return JSON.stringify(generatePattern(s)) === JSON.stringify(generatePattern(t));
}#include <stdio.h>
#include <stdbool.h>
#include <string.h>
bool generatePattern(char *s, int *pattern) {
int map[256] = {0};
int i, engine = 1;
for (i = 0; s[i]; i++) {
if (!map[s[i]]) map[s[i]] = engine++;
pattern[i] = map[s[i]];
}
return i;
}
bool isIsomorphic(char *s, char *t) {
int len = strlen(s);
int pattern_s[len], pattern_t[len];
generatePattern(s, pattern_s);
generatePattern(t, pattern_t);
for (int i = 0; i < len; i++) {
if (pattern_s[i] != pattern_t[i])
return false;
}
return true;
}using System;
using System.Collections.Generic;
public class Solution {
private List<int> GeneratePattern(string s) {
Dictionary<char, int> map = new Dictionary<char, int>();
List<int> pattern = new List<int>();
int engine = 1;
foreach (char c in s) {
if (!map.ContainsKey(c)) {
map[c] = engine++;
}
pattern.Add(map[c]);
}
return pattern;
}
public bool IsIsomorphic(string s, string t) {
return GeneratePattern(s).SequenceEqual(GeneratePattern(t));
}
}Construct a numerical pattern list for each string, marking character positions and checking for similar distributions across both pattern lists.
Time Complexity: O(n), sufficient for pattern derivation.
Space Complexity: O(1), due to bounded map size.
Approach 3: Hash Table or Array
We can use two hash tables or arrays d_1 and d_2 to record the character mapping relationship between s and t.
Traverse s and t, if the corresponding character mapping relationships in d_1 and d_2 are different, return false, otherwise update the corresponding character mapping relationships in d_1 and d_2. After the traversal is complete, it means that s and t are isomorphic, and return true.
The time complexity is O(n) and the space complexity is O(C). Where n is the length of the string s; and C is the size of the character set, which is C = 256 in this problem.
function isIsomorphic(s: string, t: string): boolean {
const d1: number[] = new Array(256).fill(0);
const d2: number[] = new Array(256).fill(0);
for (let i = 0; i < s.length; ++i) {
const a = s.charCodeAt(i);
const b = t.charCodeAt(i);
if (d1[a] !== d2[b]) {
return false;
}
d1[a] = i + 1;
d2[b] = i + 1;
}
return true;
}func isIsomorphic(s string, t string) bool {
d1 := [256]int{}
d2 := [256]int{}
for i := range s {
if d1[s[i]] != d2[t[i]] {
return false
}
d1[s[i]] = i + 1
d2[t[i]] = i + 1
}
return true
}use std::collections::HashMap;
impl Solution {
fn help(s: &[u8], t: &[u8]) -> bool {
let mut map = HashMap::new();
for i in 0..s.len() {
if map.contains_key(&s[i]) {
if map.get(&s[i]).unwrap() != &t[i] {
return false;
}
} else {
map.insert(s[i], t[i]);
}
}
true
}
pub fn is_isomorphic(s: String, t: String) -> bool {
let (s, t) = (s.as_bytes(), t.as_bytes());
Self::help(s, t) && Self::help(t, s)
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| One-to-One Character Mapping | Time Complexity: O(n), where n is the number of characters in the strings. |
| Unique Pattern Generation | Time Complexity: O(n), sufficient for pattern derivation. |
| Hash Table or Array | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| One-to-One Character Mapping | O(n) | O(k) | General case; best practical approach using hash maps to enforce bijection |
| Unique Pattern Generation | O(n) | O(n) | When comparing structural patterns of strings or explaining the concept visually |
Frequently asked questions
Is Isomorphic Strings easy or hard?
Isomorphic Strings is categorized as an Easy problem on LeetCode with an acceptance rate around 48%. The logic is straightforward once you recognize the need for a one-to-one character mapping, making it a common early practice problem for hash tables and string manipulation.
Isomorphic Strings Python/Java solution
In Python, dictionaries are used to store character mappings and sets track used characters. In Java, HashMap and HashSet serve the same role. Both implementations iterate once over the strings, validate mappings, and return false immediately if a conflict appears.
How to solve Isomorphic Strings in O(n)?
Traverse both strings simultaneously and maintain a mapping from characters in the first string to characters in the second. If a character already has a mapping, verify it matches the current character in the other string. Also track used target characters to prevent duplicates. This single pass with hash lookups gives O(n) time.
What is the best approach for Isomorphic Strings?
The best approach uses a one-to-one character mapping with hash maps. Iterate through both strings and map each character from s to t while ensuring no two characters map to the same target. Each lookup and insertion is O(1), so the full algorithm runs in O(n) time with O(k) extra space for unique characters.
Is Isomorphic Strings asked at Google/Amazon/Meta?
Isomorphic Strings is a common entry-level string and hash table problem frequently seen in interviews at companies like Amazon, Google, and Microsoft. It tests understanding of bijective mappings, hash maps, and careful constraint validation during iteration.
What data structure is used in Isomorphic Strings?
The primary data structure is a hash table (or dictionary) to store character mappings. Many solutions also use a set or a second hash map to ensure each target character is mapped only once. These structures provide O(1) lookups and updates.
What is the time complexity of Isomorphic Strings?
The optimal solution runs in O(n) time where n is the length of the strings. Each character pair is processed once and validated using constant-time hash table lookups. Space complexity is typically O(k), where k is the number of unique characters encountered.