FXTi's blog
0%

convert-sorted-array-to-binary-search-tree

Posted on Edited on

Isomorphic Strings – LeetCode 205

Problem

Description

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.

Example

Given “egg”, “add”, return true.

Given “foo”, “bar”, return false.

Given “paper”, “title”, return true.

Answer

Original

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if(s.size() != t.size()) return false;
        vector<char> map(128,0x01);
        vector<bool> reverse(128,true);
        for(unsigned i = 0; i != s.size(); ++i){
            if(map[s[i]] == 0x01){
                if(reverse[t[i]]){
                    map[s[i]] = t[i];
                    reverse[t[i]] = false;
                } else {
                    return false;
                }
            } else if (map[s[i]] != t[i]){
                return false;
            }
        }
        return true;
    }
};

思路

建立映射关系进行转换，保证单射的关系，时间复杂度$O(n)$，空间复杂度$O(1)$。
耗时$6$ ms，排名$30.65\%$

Better

思路

还没看到更好的思路。