Isomorphic Strings
Isomorphic Strings is a easy arrays & hashing problem solved with the hashing pattern.
The best approach, optimal (two-way mapping arrays), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (compare every pair of positions) up.
Problem
Two strings s and t of the same length are isomorphic if you can rename the characters of s to get t: every occurrence of a character is replaced by the same character, and two different characters are never renamed to the same one. A character may also keep its own name.
Return true if s and t are isomorphic, otherwise false.
Examples
Example 1
- Input
s = "tree", t = "moss"- Output
true- Why
- Map t -> m, r -> o, e -> s. Both copies of e become s, and no two letters share a target.
Example 2
- Input
s = "abca", t = "xyzw"- Output
false- Why
- The two a's would have to become both x and w, which is not allowed.
Example 3
- Input
s = "pq", t = "rr"- Output
false- Why
- p and q would both map to r, but two different characters may not share a target.
Constraints
1 <= s.length <= 5 * 10^4t.length == s.lengthsandtconsist of printable ASCII characters.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 14 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (compare every pair of positions) | O(n²) | O(1) |
| Optimal (two-way mapping arrays) | O(n) | O(1) |
1Brute force (compare every pair of positions)
O(n²)All n(n - 1) / 2 pairs of positions are compared.O(1)Only loop indices.Two strings are isomorphic exactly when, for every pair of positions i < j, s[i] == s[j] holds if and only if t[i] == t[j]. Check all pairs.
- For every i from 0 to n - 1 and every j from i + 1 to n - 1:
- If (s[i] == s[j]) differs from (t[i] == t[j]), return false.
- Return true.
class Solution {
public boolean isIsomorphic(String s, String t) {
int n = s.length();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
boolean sameS = s.charAt(i) == s.charAt(j);
boolean sameT = t.charAt(i) == t.charAt(j);
if (sameS != sameT) return false;
}
}
return true;
}
}class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
n = len(s)
for i in range(n):
for j in range(i + 1, n):
if (s[i] == s[j]) != (t[i] == t[j]):
return False
return Trueclass Solution {
public:
bool isIsomorphic(string s, string t) {
int n = s.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
bool sameS = s[i] == s[j];
bool sameT = t[i] == t[j];
if (sameS != sameT) return false;
}
}
return true;
}
};function isIsomorphic(s, t) {
const n = s.length;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
const sameS = s[i] === s[j];
const sameT = t[i] === t[j];
if (sameS !== sameT) return false;
}
}
return true;
}2Optimal (two-way mapping arrays)
O(n)One pass with constant work per position.O(1)Two arrays of fixed size 128, independent of n.Scan both strings once with two lookup tables: fwd[c] is the character that c from s maps to, and back[d] is the character from s that already claimed d in t. A fresh pair is recorded in both tables; a pair that contradicts either table means the answer is false.
- fwd and back are arrays of 128 zeros (0 means not mapped yet).
- For each i, let a = s[i] and b = t[i].
- If fwd[a] == 0 and back[b] == 0, set fwd[a] = b + 1 and back[b] = a + 1 (the + 1 keeps 0 free to mean unmapped).
- Otherwise, if fwd[a] != b + 1 or back[b] != a + 1, return false.
- Return true.
class Solution {
public boolean isIsomorphic(String s, String t) {
int[] fwd = new int[128];
int[] back = new int[128];
for (int i = 0; i < s.length(); i++) {
int a = s.charAt(i), b = t.charAt(i);
if (fwd[a] == 0 && back[b] == 0) {
fwd[a] = b + 1;
back[b] = a + 1;
} else if (fwd[a] != b + 1 || back[b] != a + 1) {
return false;
}
}
return true;
}
}class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
fwd = [0] * 128
back = [0] * 128
for x, y in zip(s, t):
a, b = ord(x), ord(y)
if fwd[a] == 0 and back[b] == 0:
fwd[a] = b + 1
back[b] = a + 1
elif fwd[a] != b + 1 or back[b] != a + 1:
return False
return Trueclass Solution {
public:
bool isIsomorphic(string s, string t) {
int fwd[128] = {0};
int back[128] = {0};
for (int i = 0; i < (int)s.size(); i++) {
int a = (unsigned char)s[i], b = (unsigned char)t[i];
if (fwd[a] == 0 && back[b] == 0) {
fwd[a] = b + 1;
back[b] = a + 1;
} else if (fwd[a] != b + 1 || back[b] != a + 1) {
return false;
}
}
return true;
}
};function isIsomorphic(s, t) {
const fwd = new Int32Array(128);
const back = new Int32Array(128);
for (let i = 0; i < s.length; i++) {
const a = s.charCodeAt(i), b = t.charCodeAt(i);
if (fwd[a] === 0 && back[b] === 0) {
fwd[a] = b + 1;
back[b] = a + 1;
} else if (fwd[a] !== b + 1 || back[b] !== a + 1) {
return false;
}
}
return true;
}Edge cases to test
- Single-character strings are always isomorphic
- A character may map to itself
- Two different characters in
sthat both want the same character int(only checking s -> t misses this) - One character in
sthat would need two different targets - Digits, spaces and punctuation, not only letters
Hints
Hint 1
The rule must hold in both directions: s -> t must be a function, and so must t -> s.
Hint 2
Walk both strings together and remember the partner of every character you have seen, on each side.
Hint 3
Since there are only 128 ASCII codes, two fixed-size arrays are enough for the two maps.
FAQ
What is the best time complexity for Isomorphic Strings?
Optimal (two-way mapping arrays) runs in O(n) time and O(1) extra space. One pass with constant work per position.
Which pattern does Isomorphic Strings use?
It is a arrays & hashing problem that uses the hashing pattern. Other problems with the same pattern: Group Anagrams, First Unique Character in a String, Number of Matching Subsequences.
Is there a brute force solution for Isomorphic Strings?
Yes. Brute force (compare every pair of positions) takes O(n²) time and O(1) space. Two strings are isomorphic exactly when, for every pair of positions i < j, s[i] == s[j] holds if and only if t[i] == t[j].
Which edge cases should I test for Isomorphic Strings?
Single-character strings are always isomorphic; A character may map to itself; Two different characters in s that both want the same character in t (only checking s - t misses this); One character in s that would need two different targets; Digits, spaces and punctuation, not only letters.