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.
Use hashmap, remember to check both key and value. Time complexity O(n^2), space cost O(n).
hashMap.containsValue costs O(n)
1 public class Solution { 2 public boolean isIsomorphic(String s, String t) { 3 if (s == null || t == null) 4 return false; 5 if (s.length() != t.length()) 6 return false; 7 if(s.length()==0 && t.length()==0) 8 return true; 9 int length = s.length(); 10 Map<Character, Character> map = new HashMap<Character, Character>(); 11 for (int i = 0; i < length; i++) { 12 char tmp1 = s.charAt(i); 13 char tmp2 = t.charAt(i); 14 if (map.containsKey(tmp1)) { 15 if (map.get(tmp1) != tmp2) 16 return false; 17 } else if (map.containsValue(tmp2)) { 18 return false; 19 } else { 20 map.put(tmp1, tmp2); 21 } 22 } 23 return true; 24 } 25 }
Use extra space to reduce time complexity.
1 public class Solution { 2 public boolean isIsomorphic(String s, String t) { 3 if (s == null || t == null) 4 return false; 5 if (s.length() != t.length()) 6 return false; 7 if(s.length()==0 && t.length()==0) 8 return true; 9 int length = s.length(); 10 Map<Character, Character> map = new HashMap<Character, Character>(); 11 Set<Character> counts = new HashSet<Character>(); 12 for (int i = 0; i < length; i++) { 13 char tmp1 = s.charAt(i); 14 char tmp2 = t.charAt(i); 15 if (map.containsKey(tmp1)) { 16 if (map.get(tmp1) != tmp2) 17 return false; 18 } else if (counts.contains(tmp2)) { 19 return false; 20 } else { 21 map.put(tmp1, tmp2); 22 counts.add(tmp2); 23 } 24 } 25 return true; 26 } 27 }
原文：http://www.cnblogs.com/ireneyanglan/p/4806088.html