Fork me on GitHub

leetcode之205. 同构字符串

发表于 | 分类于
字数统计 261 字 | 阅读时长 1 分钟

题目描述：

给定两个字符串 *s* 和 t，判断它们是否是同构的。

如果 *s* 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身。

示例 1:

1
2
3
> 输入: s = "egg", t = "add"
> 输出: true
>

示例 2:

1
2
3
> 输入: s = "foo", t = "bar"
> 输出: false
>

示例 3:

1
2
3
> 输入: s = "paper", t = "title"
> 输出: true
>

说明:
你可以假设 *s* 和 t 具有相同的长度。

解题思路：

时间复杂度：$O(n)$, 空间复杂度:$O(1)$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isIsomorphic(string s, string t) {
        map<char, int> mp1,mp2;

        if(s.size() == 0) return true;

        for(int i = 0; i < s.length(); i++)
        {
             mp1[s[i]] = mp2[t[i]] = -1;
        }
        for(int i = 0; i < s.length(); i++)
        {
               if(mp1[s[i]] != mp2[t[i]]) return false;
               else mp1[s[i]] = mp2[t[i]] = i;
        }            
        return true;
    }
};