leetcode解题: Isomorphic Strings (205)

发表于 | 分类于

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.

解法1：

用hashmap， 要注意的是，除了有aa->ab情况要排除，还有ab->aa的情况也要排除，所以这里用到了两个hashmap。
C++
C++里hashmap查看是否有key也可以用map.count(key)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.size() != t.size()) {
            return false;
        }
        if (s.empty()) {
            return true;
        }
        
        unordered_map<char, char> mapLeft;
        unordered_map<char, char> mapRight;
        for (int i = 0; i < s.size(); ++i) {
            auto left2Right = mapLeft.find(s[i]);
            auto right2Left = mapRight.find(t[i]);
            if (left2Right == mapLeft.end() && right2Left == mapRight.end()) {
                mapLeft[s[i]] = t[i];
                mapRight[t[i]] = s[i];
            } else if (left2Right != mapLeft.end()) {
                if (mapLeft[s[i]] != t[i]) {
                    return false;
                }
                mapRight[t[i]] = s[i];
            } else if (right2Left != mapRight.end()) {
                if (mapRight[t[i]] != s[i]) {
                    return false;
                }
                mapLeft[s[i]] = t[i];
            } else if (mapLeft[s[i]] != t[i] || mapRight[t[i]] != s[i]) {
                return false;
            }
        }
        
        return true;
    }
};

Java

1