Java solution with two hash maps and guaranted O(N) running time


  • 0
    J

    Here is the java solution that uses two hash map:

    public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if(s == null || t == null) {
            return false;
        } else if(s.length() != t.length()) {
            return false;
        }
    
        final Map<Character, Character> chars = new HashMap<Character, Character>();
        final Map<Character, Character> reverse = new HashMap<Character, Character>();
    
        for(int ind = 0; ind < s.length(); ind++) {
    
            final char src = s.charAt(ind);
            final char des = t.charAt(ind);
    
            if(!chars.containsKey(src) && !reverse.containsKey(des)) {
                chars.put(src, des);
                reverse.put(des, src);
            } else {
                if((chars.containsKey(src) && chars.get(src) != des)
                        || (reverse.containsKey(des) && reverse.get(des) != src)) {
                    return false;
                }
            }
        }
        return true;
    }
    }
    
    • first one is used to store the two coresponding characters
    • second one stores the reversed mapping two guarantee that no two characters maps to the same one i.e. 'aa' is not isomorphic with 'ab'.

  • 1
    K

    Your solution seems legit, but I guess to further optimize the solution you can use two char arrays of size 256 each of the maps.

    Happy coding!


Log in to reply
 

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