One-one mapping solution in Java


  • 1
    B

    I used two maps for the one-one mapping relation for the two strings. This may waste more memory, but the logic is really simple.

    public boolean isIsomorphic(String s, String t) {
        if(s == null)
            return t == null;
        
        Map<Character, Character> map = new HashMap<>(), 
                mapR = new HashMap<>();
        for(int i = 0; i < s.length(); i++){
            char cS = s.charAt(i), cT = t.charAt(i);
            map.putIfAbsent(cS, cT);
            mapR.putIfAbsent(cT, cS);
            if(map.get(cS) != cT || mapR.get(cT) != cS)
                return false;
        }
        return true;
    }

  • 0
    L

    Actually we can just use one map like this

        Map<Character,Character> map = new HashMap<Character,Character>();
        int len = 0;
        while (len < s.length()) {
            if (map.containsKey(s.charAt(len)) && map.get(s.charAt(len)) != t.charAt(len)) {
                return false;
            } else if (!map.containsKey(s.charAt(len)) && map.containsValue(t.charAt(len))){
                return false;
            }
            map.put(s.charAt(len), t.charAt(len));
            len++;
        }
        return true;
    

  • 0

    What is the runtime complexity of containsValue?


  • 0
    B

    This is the code from sun jdk1.7. so is o(n) time:

    public boolean containsValue(Object value) {
        if (value == null)
            return containsNullValue();
    
        Entry[] tab = table;
        for (int i = 0; i < tab.length ; i++)
            for (Entry e = tab[i] ; e != null ; e = e.next)
                if (value.equals(e.value))
                    return true;
        return false;
    }
    

Log in to reply
 

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