Isomorphic Strings

Rroblem

Given two strings s and t, determine if they are isomorphic.

Two strings 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.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note: You may assume both s and t have the same length.

Solution

O(n) time O(1) space Solution

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s == null || t == null) return true;
        int[] ss = new int[256], ts = new int[256];
        int mark = 1;
        for (int i = 0; i < s.length(); i++) {
            if (ss[s.charAt(i)] != ts[t.charAt(i)]) return false;
            ss[s.charAt(i)] = mark;
            ts[t.charAt(i)] = mark;
            mark++;
        }
        return true;
    }
}

Analysis

This problem should have a HashMap solution which, however, will take O(n) space
In our solution, we use two int[256] to record the appearance of each character in given strings
If their corresponding values are different, we return false Otherwise, we set the values with mark and then update mark by increment one
Notice that, we init mark = 1 cause the default value in array is always 0