O(n) time and space Java solution with one hashmap


  • -1
    J
    public class Solution {
        public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        HashMap<Character, Character> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if(map.containsKey(s.charAt(i))){
                if(t.charAt(i) != map.get(s.charAt(i))){
                    return false;
                }
            }else{
                if(map.containsValue(t.charAt(i))){
                    return false;
                }
            }
            map.put(s.charAt(i), t.charAt(i));
        }
        return true;
        }
    }

  • 0
    B

    This is O(n^2). containsValue is definitely not O(1). You are using hashes which can only retrieve a value at O(1) if the key is known. Otherwise the hash has to be iterated, which is O(n).


Log in to reply
 

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