Isomorphic Strings

https://leetcode.com/problems/isomorphic-strings/description/

Given two stringssandt, determine if they are isomorphic.

Two strings are isomorphic if the characters inscan be replaced to gett.

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 bothsandthave the same length.

Thoughts

两个单词的字母应是一一映射的关系，判断是否满足。那就一边遍历一边画映射，当发现一个字符不满足已经画过得映射则报错。

Code

class Solution {
    public boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }

        Map<Character, Character> map =  new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            if (map.containsKey(s.charAt(i)) && map.get(s.charAt(i)) != t.charAt(i)) {
                return false;
            } else if (!map.containsKey(s.charAt(i)) && map.containsValue(t.charAt(i))) {
                return false;
            }
            map.put(s.charAt(i), t.charAt(i));
        }

        return true;
    }
}

Analysis

做题耗时8分

Errors:

1. 没写if (!map.containsKey(s.charAt(i)) && map.containsValue(t.charAt(i))) 忘了[a, b]和[a,a]， 只检查了一边映射。

时间复杂度O(n), 空间O(n).