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.

思路:建立s->t的hashtable, 用hashset检查t中的char不会被映射2次

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length() ) return false;
        if (s == null || t == null) return false;
        HashMap<Character, Character> map = new HashMap<>(); // build mapping table based on s -> t
        HashSet<Character> set = new HashSet<>(); // keep track of char in t

        for (int i = 0; i < s.length(); i ++) {
            if (!map.containsKey(s.charAt(i))) {
                if(set.contains(t.charAt(i))) {
                    return false;
                } else {
                    map.put(s.charAt(i), t.charAt(i));
                    set.add(t.charAt(i));
                }

            } else {
                Character value = map.get(s.charAt(i));
                if(value != t.charAt(i)) {
                    return false;
                } 
            }

        }
        return true;
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s