Star

Leetcode: 205. Isomorphic Strings

Posted on | In |

Question

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.

Explaination

方法一：用Hashmap存对应的字符，并用一个HashSet存用过的替代字符。 方法二：用hashtable，两个数组，变化里面的frequency，如果不再一样，就不成立。

Code

Solution 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public boolean isIsomorphic(String s, String t) {
    HashMap<Character, Character> map = new HashMap<>();
    HashSet<Character> set = new HashSet<>();
    if (s.length() != t.length()) return false;
    for (int i=0; i<s.length(); i++) {
        if (map.containsKey(s.charAt(i))) {
            if (map.get(s.charAt(i)) != t.charAt(i)) {
                return false;
            }
        } else {
            if (set.contains(t.charAt(i))) return false;
            set.add(t.charAt(i));
            map.put(s.charAt(i), t.charAt(i));
        }
    }
    return true;
}

Solution 2

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] m1 = new int[256];
        int[] m2 = new int[256];
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            if (m1[s.charAt(i)] != m2[t.charAt(i)]) return false;
            m1[s.charAt(i)] = i + 1;
            m2[t.charAt(i)] = i + 1;
        }
        return true;
}
}