题目

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

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

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

示例 1:

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

示例 2:

输入: s = "foo", t = "bar"
输出: false

示例 3:

输入: s = "paper", t = "title"
输出: true

说明:

可以假设 s 和 t 具有相同的长度。

方案一

func isIsomorphic(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }

    s_mode := getMode(s)
    t_mode := getMode(t)
    for i := 0; i < len(s); i++ {
        if s_mode[i] != t_mode[i] {
            return false
        }
    }
    return true
}

func getMode(str string) []int {
    // 获取字符串模式 paper -> [0, 1, 0, 2, 3] <- title
    m := map[rune]int{}
    mode := []int{}
    num := 0
    for _, s := range str {
        if _, ok := m[s]; !ok {
            m[s] = num
            num += 1
        }
        mode = append(mode, m[s])
    }

    return mode
}
  • 时间复杂度 $O(3N)$

重构在一个函数中实现可以实现时间复杂度为 $O(N)$ 的算法，但是没有上述容易理解。

mode 如果使用字符串（01023）表示的话，虽然比较起来时间复杂度相同，但是写法上会更简单。

方案二

对比两个字符串对应位置的字符在字符串内第一次出现的位置。

class Solution {
  public:
    bool isIsomorphic(string s, string t) {
        for(int i=0;i<s.size();i++){
            if(s.find(s[i]) != t.find(t[i]))
            return false;
        }
        return true;
    }
};

上述为 leetcode 讨论区解法

原文

https://leetcode-cn.com/explore/learn/card/hash-table/205/practical-application-hash-map/812/