LeetCode205. Isomorphic Strings（模拟）

Easy
Accepted：184,532
Submissions：504,651

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 1:

Input: s = "egg", t = "add"
Output: true

Example 2:

Input: s = "foo", t = "bar"
Output: false

Example 3:

Input: s = "paper", t = "title"
Output: true

Note:

You may assume both s and t have the same length.

链接

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

题意

给定两个字符串s和t，判断它们是不是同构的。同构的定义是：寻找到一个字符集到字符集的映射，使得通过这个字符集的映射，s可以转变为t。注意没有两个字符可以映射到相同的字符，但字符可以映射到自身。s和t的长度相同。

题解

使用两个map，可以将s和t中的字符与数字建立映射关系，然后判断相同字符是否相等。完整的解释如下：

The idea is that we need to map a char to another one, for example, "egg" and "add", we need to constract the mapping 'e' -> 'a' and 'g' -> 'd'. Instead of directly mapping 'e' to 'a', another way is to mark them with same value, for example, 'e' -> 1, 'a'-> 1, and 'g' -> 2, 'd' -> 2, this works same.
So we use two arrays here m1 and m2, initialized space is 256 (Since the whole ASCII size is 256, 128 also works here). Traverse the character of both s and t on the same position, if their mapping values in m1 and m2 are different, means they are not mapping correctly, returen false; else we construct the mapping, since m1 and m2 are both initialized as 0, we want to use a new value when i == 0, so i + 1 works here.

不过要注意一下a character may map to itself的情况需要考虑清楚，比如fab和baa这种是false。

代码

Runtime: 8 ms, faster than 97.62% of C++ online submissions for Isomorphic Strings.
Memory Usage: 9 MB, less than 100.00% of C++ online submissions for Isomorphic Strings.

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        int n = s.length();
        int map1[256] = {0}, map2[256] = {0};
        for (int i = 0; i < n; ++i)
        {
            if (map1[s[i]] != map2[t[i]]) // 最开始均为0
                return false;
            map1[s[i]] = i + 1; // 映射到同一个数字
            map2[t[i]] = i + 1;
        }
        return true;
    }
};

The end.
2019年2月15日星期五