Java solution using HashMap


  • 35
    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;
            
        }
    }

  • 11
    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!

  • 0
    L
    public boolean isIsomorphic(String s, String t) {
            if (s == null || t == null) return false;
            if (s.length() != t.length()) return false;
            
            Map<Character, Integer> mapS = new HashMap<Character, Integer>();
            Map<Character, Integer> mapT = new HashMap<Character, Integer>();
            
            for (int i = 0; i < s.length(); i++) {
                int indexS = mapS.getOrDefault(s.charAt(i), -1);
                int indexT = mapT.getOrDefault(t.charAt(i), -1);
                            
                if (indexS != indexT) {
                    return false;
                }
                
                mapS.put(s.charAt(i), i);
                mapT.put(t.charAt(i), i);
            }
            
            return true;
        }
    

    Two strings are isomorphic if the positions of the characters follow the same pattern. So I'm using maps to compare the position patterns.


Log in to reply
 

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