LeetCode205. Isomorphic Strings(模拟)

2019 年 02 月 15 日 • 阅读: 936 • LeetCode阅读设置

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


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






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的情况需要考虑清楚,比如fabbaa这种是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 {
    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日 星期五