Java solution using HashMap


  • 33
    S
    public class Solution {
        public boolean isIsomorphic(String s, String t) {
            if(s == null || s.length() <= 1) return true;
            HashMap<Character, Character> map = new HashMap<Character, Character>();
            for(int i = 0 ; i< s.length(); i++){
                char a = s.charAt(i);
                char b = t.charAt(i);
                if(map.containsKey(a)){
                     if(map.get(a).equals(b))
                    continue;
                    else
                    return false;
                }else{
                    if(!map.containsValue(b))
                    map.put(a,b);
                    else return false;
                    
                }
            }
            return true;
            
        }
    }

  • 9
    W

    No,this solution is O(N*N), because of the containsValue() method! Every search of containsValue() is O(N).


  • 0
    R

    Hi
    can you tell me what is wrong in my code? I tried to write it in C++, but mine is wrong, thanks

    class Solution {
    public:
        bool isIsomorphic(string s, string t) {
            unordered_map<char,char>table;
            for(int i=0; i<s.size(); ++i){
                if(table.count(s[i])){
                    if(table[s[i]]!=t[i]) return false;
                }
                else{
                    if(!table.count(t[i])) table[s[i]]=t[i];
                    else                   return false;
                }
            }
            return true;
        }
    };

  • 0

    the value could be stored in a HashSet object so the time efficiency becomes O(n)


  • -2
    C

    It's O(1) for containsValue() in hashmap


  • 0
    Z

    I think the containValue() is O(n)
    http://stackoverflow.com/questions/16757359/what-is-the-time-complexity-of-hashmap-containsvalue-in-java
    you need to iterate through the (key,value) pair to find the value you want, that's why it's O(n).


  • 0
    M

    I first used map.get(a) != b instead of !map.get(a).equals(b), and it's not working. Could anyone clarify why it happens?


  • 0
    B

    @mengmengli815 map.get(a) return object of type Character. you might want to cast it to char before comparing.


  • 0
    V
    This post is deleted!

Log in to reply
 

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