205. Isomorphic Strings

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example,
Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note:
You may assume both s and t have the same length.

Solution:

Use a HashMap to map the char in s to char in t and use a hashset to track all the chars appeared and have been mapped to s previously. Of course we can use Hashmap.containsValue to check that, but it is not efficient. 

The hashset is to avoid misjudging this situation 'pt' => 'aa', which I failed to check in my first try.

  public boolean isIsomorphic(String s, String t) {  
    HashMap<Character,Character> map=new HashMap();  
    HashSet<Character> set=new HashSet();  
    for(int i=0;i<s.length();i++){  
      char c=s.charAt(i);  
      char d=t.charAt(i);  
      if(map.containsKey(c)){  
        if(d!=map.get(c)) return false;  
      }  
      else if(set.contains(d)) return false;  
      else{  
        map.put(c,d);  
        set.add(d);  
      }  
    }  
     return true;  
   }  

Another technique is to use two maps to track all the characters and corresponding position for each string, so if  sMap contains current char in s and tMap contains current char in t, but their position is not the same which means these two chars are not mapped to each other previously, so they are not isomorphic strings.
You can use two int arrays to track the positions as well because there are finite number of chars.

  public boolean isIsomorphic(String s, String t) {  
    HashMap<Character,Integer> sMap=new HashMap();  
    HashMap<Character,Integer> tMap=new HashMap();  
    for(int i=0;i<s.length();i++){  
      char c=s.charAt(i);  
      char d=t.charAt(i);  
      if(sMap.containsKey(c) && tMap.containsKey(d)){  
         if(sMap.get(c)!=tMap.get(d))return false;  
      }  
      else if(!sMap.containsKey(c) && !tMap.containsKey(d)){  
        sMap.put(c,i);  
        tMap.put(d,i);  
      }  
      else return false;  
    }  
     return true;  
   }