Easy Understanding Java code with HashMap


  • 1
    L
        if(s.length() == 0) return true;
    
        Map<Character, Integer> m1 = new HashMap<Character, Integer>();
        Map<Character, Integer> m2 = new HashMap<Character, Integer>();
    
        for(int i = 0; i < s.length(); i++) {
            if(!m1.containsKey(s.charAt(i))) m1.put(s.charAt(i), i);
            if(!m2.containsKey(t.charAt(i))) m2.put(t.charAt(i), i);
            if(m1.size() != m2.size()) {
                return false;
            } else {
                if(m1.get(s.charAt(i)) != m2.get(t.charAt(i))) return false;
            }
        }
    
        return true;

  • 0
    A
    This post is deleted!

  • 4
    A

    you can simplify it to use a single hashmap, more efficient

    import java.util.*;
    public class Solution {
        public boolean isIsomorphic(String s, String t) {
            HashMap<Character, Character> charMap = new HashMap<Character, Character>();
            for(int i = 0; i < s.length(); i++)
            {
                if (charMap.containsKey(s.charAt(i)))
                {
                    if (t.charAt(i) != charMap.get(s.charAt(i)))
                         return false;
                }
                else if (charMap.containsValue(t.charAt(i)))
                    return false;
                else
                    charMap.put(s.charAt(i), t.charAt(i));
            }
            return true;
        }
    }

  • 0
    L

    I've got it. Thank you very much!


  • 0
    S

    hashmap.containsValue() takes O(N) time, so your algorithm works in O(N2) in the worst case. Why is it more efficient?


  • 0
    L

    8ms - O(n)

    public class Solution {
        public boolean isIsomorphic(String s, String t) {
            if(s.length() != t.length()) return false;
    
            int N = s.length();
            int[] mst = new int[256];
            int[] mts = new int[256];
            
            for(int i = 0; i < N; i++) {
                char cs = s.charAt(i);
                char ct = t.charAt(i);
                
                if((mst[cs] == 0) && (mts[ct] == 0)) {
                    mst[cs] = ct;
                    mts[ct] = cs;
                }
                
                if((mst[cs] != ct) || (mts[ct] != cs)) 
                    return false;
            }
            
            return true;
        }
    }

Log in to reply
 

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