Practice › Strings
Isomorphic Strings
Easy · Strings · Asked at Amazon, Google, LinkedIn
Strings s and t are isomorphic if the characters of s can be replaced one-to-one to get t (no two characters map to the same character). Print YES or NO.
Input
Two lines: s and t (same length, lowercase letters).
Output
YES or NO.
Constraints
- 1 ≤ |s| = |t| ≤ 10^5
Example 1
Input
egg add
Output
YES
Example 2
Input
foo bar
Output
NO
Hints
- Each character of s must always map to the same character of t.
- Also check the reverse direction — two different characters of s can't map to the same character of t. Keep two maps.
Approach
Keep sToT and tToS (arrays of 26 entries, empty at first). For each position i: if either map already holds a different partner for s[i] or t[i], answer NO. Otherwise record both directions. Checking only one direction would wrongly accept "ab" → "aa".
Complexity: O(n) time · O(1) extra space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
string s, t;
cin >> s >> t;
vector<int> st(26, -1), ts(26, -1);
bool ok = s.size() == t.size();
for (size_t i = 0; ok && i < s.size(); i++) {
int a = s[i] - 'a', b = t[i] - 'a';
if ((st[a] != -1 && st[a] != b) || (ts[b] != -1 && ts[b] != a)) ok = false;
st[a] = b;
ts[b] = a;
}
cout << (ok ? "YES" : "NO") << "\n";
return 0;
}Python solution
s = input().strip()
t = input().strip()
s_to_t, t_to_s = {}, {}
ok = len(s) == len(t)
for a, b in zip(s, t):
if s_to_t.setdefault(a, b) != b or t_to_s.setdefault(b, a) != a:
ok = False
break
print("YES" if ok else "NO")Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next(), t = sc.next();
int[] st = new int[26], ts = new int[26];
Arrays.fill(st, -1);
Arrays.fill(ts, -1);
boolean ok = s.length() == t.length();
for (int i = 0; ok && i < s.length(); i++) {
int a = s.charAt(i) - 'a', b = t.charAt(i) - 'a';
if ((st[a] != -1 && st[a] != b) || (ts[b] != -1 && ts[b] != a)) ok = false;
st[a] = b;
ts[b] = a;
}
System.out.println(ok ? "YES" : "NO");
}
}