闯关leetcode——205. Isomorphic Strings

大纲

题目
- 地址
- 内容
解题
- 代码地址

题目

地址

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

内容

Given two strings s and t, determine if they are isomorphic.

Two strings s and t 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
Explanation:
The strings s and t can be made identical by:
Mapping ‘e’ to ‘a’.
Mapping ‘g’ to ‘d’.

Example 2:

Input: s = “foo”, t = “bar”
Output: false
Explanation:
The strings s and t can not be made identical as ‘o’ needs to be mapped to both ‘a’ and ‘r’.

Example 3:

Input: s = “paper”, t = “title”
Output: true

Constraints:

1 <= s.length <= 5 * 10⁴
t.length == s.length
s and t consist of any valid ascii character.

解题

这题就是要对比两个字符串的结构是否一致。简单点说，两个字符串中的字符要有确定的一一对应关系。

这个一一对应是双向的，而不是单向的。比如ab和cc就不是双向映射的，因为第二个串中的c既可以对应第一个串中的a，又可以对应b。

因为只有ASCII码，所以我们只要256长度的数组来记录它们的对应关系（下标是源ASCII码的值，值是另一个字符串中对应位置的ASCII码值）。

又由于要求双向的一一对应，所以使用2个256长度的数组来做记录。

只要出现非双向一一对应关系，就返回false。

#include <vector>
#include <string>
using namespace std;

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector<int> s2t(256, -1);
        vector<int> t2s(256, -1);
        for (int i = 0; i < s.size(); i++) {
            if (s2t[s[i]] == -1) {
                if (t2s[t[i]] != -1) {
                    return false;
                }
                s2t[s[i]] = t[i];
            } 
            else if (s2t[s[i]] != t[i]) {
                return false;
            } 

            if (t2s[t[i]] == -1) {
                t2s[t[i]] = s[i];
            }
        }
        return true;
    }
};