Short Java solution without maps


  • 76
    S

    Hi guys!

    The main idea is to store the last seen positions of current (i-th) characters in both strings. If previously stored positions are different then we know that the fact they're occuring in the current i-th position simultaneously is a mistake. We could use a map for storing but as we deal with chars which are basically ints and can be used as indices we can do the whole thing with an array.

    Check the code below. Happy coding!


    public class Solution {
        public boolean isIsomorphic(String s1, String s2) {
            int[] m = new int[512];
            for (int i = 0; i < s1.length(); i++) {
                if (m[s1.charAt(i)] != m[s2.charAt(i)+256]) return false;
                m[s1.charAt(i)] = m[s2.charAt(i)+256] = i+1;
            }
            return true;
        }
    }

  • 7
    W
    public boolean isIsomorphic(String s, String t) {
    	int[] map = new int[128];
    	int[] book = new int[128];
    	for (int i = 0; i < s.length(); i++) {
    		int cs = (int) s.charAt(i);
    		int ts = (int) t.charAt(i);
    		if (map[cs] == 0 && book[ts] == 0) {
    			map[cs] = ts;
    			book[ts] = 1;
    		} else if (map[cs] != ts)
    			return false;
    	}
    	return true;
    }
    

    yours are good !


  • 3
    G

    that's just awesome! But what if the char is Chinese char like ‘中’?


  • 1
    S

    yeah, you're right, my solution will work only for ASCII. :) For Unicode we need much bigger arrays - of length 2^16 I suppose for two bytes. But the logic could be the same.


  • 0
    L

    why 512? (12 characters12 characters


  • 3
    K

    because the length of ASCII is 256


  • 0
    N

    why m[s1.charAt(i)] = m[s2.charAt(i)+256] = i+1? why not m[s1.charAt(i)] = m[s2.charAt(i)+256] = i;
    thanks


  • 0
    J

    you can try "m[s1.charAt(i)] = m[s2.charAt(i)+256] = i;" and you will know the reason from error information


  • 12
    C

    The statement wants to mark each character modified in that array with a distinct value. And 0 is the default value, so we should not use it, otherwise we cannot distinguish between the default maker and the the marker we made. For example, "aa" and "ab", in the first loop(i=0), if m[a]=0 and m[a+256]=0, then in the second loop, we cannot distinguish between m[a]=0 and m[b+256]=0. In fact, the m[a] has been modified in the first loop. So it will fail as in the leetcode case.


  • 0
    G

    As the default value of array is zero, we cannot distinguish default value and the last seen position if the last seen position is at 0. So, we should use one-based index instead of zero-based. As array uses zero-based index, we should use i+1 as the last seen position.


  • 0
    Y

    @shpolsky Your solution is pretty. But I think we can do the iteration from end to start to avoid that i+1 operation. The character at index 0 will not be confused with the default value since it is the last operation.

    for (int i = s1.length()-1; i > -1; i--) {
        if (m[s1.charAt(i)] != m[s2.charAt(i)+256]) return false;
            m[s1.charAt(i)] = m[s2.charAt(i)+256] = i;
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.