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

• 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;
}
``````

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