Java solution with comments O(n)


  • 0
    B
    public class Solution {
    public boolean isIsomorphic(String s, String t) {
      int  len=s.length();
        if(len==0) return true; 
        HashMap<Character, Character> map= new HashMap<Character,Character>();
        for(int i=0; i<len;i++)
        { char ch1=t.charAt(i); char ch2=s.charAt(i);
          if(map.containsKey(ch1))  //if a mapping exist, campare current pair with mapping.
          {char temp=map.get(ch1);
             if(temp!=ch2) return false; 
          }
          else if(map.containsValue(ch2)){return false;} // make sure the current value is not taken 
          else {map.put(ch1,ch2);} //push to hashmap
            
        }
        return true;
    }
    

    }


  • 0
    B

    HashMap containsValue() is O(n), so your solution is O(n^2).


  • 0
    B

    In average case, search in HashMap only take O(1). Only when collision happens, it uses a linked list format to search that takes O(n).


  • 0
    B

    You should be clear of the difference with the Map 'key' and the 'value'.


  • 0
    B

    OK. I did a search. You are right. So to decrease the time complexity. I think I would create two hashmap to replace "containsValue" with "containsKey".
    Thank you.


Log in to reply
 

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