Java 2 solutions Both O(n), using Map, without Map


  • 1
    M

    Using map:

    I think the solution "Java solution using Map" by screddy is O(n^2), because containsValue() in HashMap is O(n). In this method, s will map t and t will map to s. If both is true, return true.

    Considering "add" "hhh", if only do map once, it will return true.

        public boolean isIsomorphic(String s, String t) {
            if(s==null && t==null) return true;
            if(s==null || t==null || s.length()!=t.length()) return false;
            return isIsomorphic_helper(s, t) && isIsomorphic_helper(t, s);
        }
        private boolean isIsomorphic_helper(String s, String t){
            final int N = s.length();
            Map<Character, Character> map = new HashMap<>();
            char c1, c2; 
            for(int i=0; i<N; i++){
                c1 = s.charAt(i);
                c2 = t.charAt(i);
                if(map.containsKey(c1)){
                    if(map.get(c1)!=c2) return false;
                } else {
                    map.put(c1, c2);
                }
            }
            return true;
        }
    
    

    Without map:
    Assume all characters in string s and t belong to ascii code instead of Unicode.

        /**
        If assuming s.length() < Integer.MAX_VALUE, U change m1 and m2 to int array.
        */  
        public boolean isIsomorphic(String s, String t) {
            if(s==null && t==null) return true;
            if(s==null || t==null || s.length()!=t.length()) return false;
            long[] m1 = new long[256]; // ascii code is from 0 to 255
            long[] m2 = new long[256];
            long count = 1;
            char c1, c2;
            for(int i=0; i<s.length(); i++){
                c1 = s.charAt(i);
                c2 = t.charAt(i);
                if(m1[c1]!=m2[c2]) return false;
                m1[c1] = count;
                m2[c2] = count; 
                count++;
            }
            return true;
        }
    

Log in to reply
 

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