Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

Example 1

Input

egg
add

Output

YES

Example 2

Input

foo
bar

Output

NO

Hints

  1. Each character of s must always map to the same character of t.
  2. 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");
    }
}

Solve Isomorphic Strings online · All practice problems