Question

Formatted question description: https://leetcode.ca/all/205.html

 205	Isomorphic Strings

 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.

 Example 1:

 Input: s = "egg", t = "add"
 Output: true

 Example 2:

 Input: s = "foo", t = "bar"
 Output: false

 Example 3:

 Input: s = "paper", t = "title"
 Output: true

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

Algorithm

Two HashMaps are used to record the occurrence of characters in the original string and the target string. Since the ASCII code has only 256 characters, a 256-size array can be used to replace the HashMap and initialize it to 0 to traverse the original string.

Take a character from the source string and the target string, and then look up its value in the two arrays respectively. If they are not equal, return false. If they are equal, update its value to i + 1.

Code

Java

import java.util.Arrays;

public class Isomorphic_Strings {

    class Solution {
        public boolean isIsomorphic(String s, String t) {

            if (s == null || t == null || s.length() != t.length()) {
                return false;
            }

            int[] sLastSeen = new int[256];
            int[] tLastSeen = new int[256];

            Arrays.fill(sLastSeen, -1);
            Arrays.fill(tLastSeen, -1);

            for (int i = 0; i < s.length(); i++) {
                char sChar = s.charAt(i);
                char tChar = t.charAt(i);

                // @note: either is >0. including case one is >0 the other is <0
                if (sLastSeen[sChar] >= 0 || tLastSeen[tChar] >= 0) {
                    if (sLastSeen[sChar] != tLastSeen[tChar]) {
                        return false;
                    }
                }

                sLastSeen[sChar] = i;
                tLastSeen[tChar] = i;
            }

            return true;
        }
    }
}

All Problems

All Solutions