63 - 同构字符串

题目

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

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

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

示例 1:

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

示例 2:

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

示例 3:

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

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

解答

两个字典

作者：vailing

链接：https://leetcode-cn.com/problems/isomorphic-strings/solution/jiao-cha-ying-she-by-vailing/

建立一个哈希表来放对应

但一个表不能避免ab对应aa的情况，因此就再建一个表，对应相反的。

var isIsomorphic = function (s, t) {
  if (s.length !== t.length) {
    return false
  }
  let smap = {}
  let tmap = {}
  for (let i = 0; i < s.length; i++) {
    if (smap.hasOwnProperty(s[i]) && smap[s[i]] != t[i]) {
      return false
    }
    if (tmap.hasOwnProperty(t[i]) && tmap[t[i]] != s[i]) {
      return false
    }
    smap[s[i]] = t[i]
    tmap[t[i]] = s[i]
  }
  return true
};

Runtime: 92 ms, faster than 9.57% of JavaScript online submissions forIsomorphic Strings.

Memory Usage: 36.8 MB, less than 29.41% of JavaScript online submissions for Isomorphic Strings.

速度有点慢哈

用map代替obj，也许能好一点点

var isIsomorphic = function (s, t) {
  if (s.length !== t.length) {
    return false
  }
  let smap = new Map()
  let tmap = new Map()
  for (let i = 0; i < s.length; i++) {
    if (smap.has(s[i]) && smap.get(s[i]) != t[i]) {
      return false
    }
    if (tmap.has(t[i]) && tmap.get(t[i]) != s[i]) {
      return false
    }
    smap.set(s[i], t[i])
    tmap.set(t[i], s[i])
  }
  return true
};

Runtime: 76 ms, faster than 30.57% of JavaScript online submissions for Isomorphic Strings.

Memory Usage: 36.5 MB, less than 52.94% of JavaScript online submissions for Isomorphic Strings.

看到另一种解法：

作者：ldq-2

链接：https://leetcode-cn.com/problems/isomorphic-strings/solution/205tong-gou-zi-fu-chuan-javascript-jie-ti-by-ldq-2/

var isIsomorphic = function (s, t) {
  if (s.length !== t.length) {
    return false
  }
  let smap = new Map()
  let tmap = new Map()
  for (let i = 0; i < s.length; i++) {
    if (smap.has(s[i]) || tmap.has(t[i])) {
      if (smap.get(s[i]) !== tmap.get(t[i])) {
        return false
      }
    }
    smap.set(s[i], i)
    tmap.set(t[i], i)

  }
  return true
};

Runtime: 100 ms, faster than 6.74% of JavaScript online submissions for Isomorphic Strings.

Memory Usage: 35.8 MB, less than 70.59% of JavaScript online submissions for Isomorphic Strings.

内存占用得少，可能是因为判断没那么复杂了吧

indexof

这个骚操作说的是，不用管映射，如果两个字符串是同构的，那么他们的结构就是一样的。s重复字母的地方，t也会重复字母。

var isIsomorphic = function (s, t) {
  if (s === t || s === '') {
    return true;
  }
  for (let i = 0; i < s.length - 1; i++) {
    if (s.indexOf(s[i], i + 1) !== t.indexOf(t[i], i + 1)) {
      return false
    }
  }
  return true
};

Runtime: 56 ms, faster than 95.90% of JavaScript online submissions for Isomorphic Strings.

Memory Usage: 35.2 MB, less than 88.24% of JavaScript online submissions for Isomorphic Strings.

indexOf能返回某个指定的字符串值在字符串中首次出现的位置。

第一个参数是要找的那串字符，在这里就是一个字母；第二个参数是开始检索的位置，最多到length-1

所以，如果字母后面有重复，而且重复的位置一样，那么就算通过；如果有重复，但地方不一样，那么结构就不一样。

感觉这是一下子击中了本质的做法😂😂

go

func isIsomorphic(s string, t string) bool {
    if len(s) != len(t) {
        return false
    }
    smap := make(map[uint8]uint8)
    tmap := make(map[uint8]uint8)
    for i := 0; i < len(s); i++ {
        if _, ok := smap[s[i]]; ok && smap[s[i]] != t[i] {
            return false
        }
        if _, ok := tmap[t[i]]; ok && tmap[t[i]] != s[i] {
            return false
        }
        smap[s[i]] = t[i]
        tmap[t[i]] = s[i]
    }
    return true
}

Runtime: 8 ms, faster than 13.98% of Go online submissions forIsomorphic Strings.

Memory Usage: 2.7 MB, less than 100.00% of Go online submissions for Isomorphic Strings.

go里面可以一个个取字符串，不过取出来的是其对应的utf-8的值，比如1对应的是49

不过无所谓，反正存的值是不会变的，只是类型定义的时候，存进去的就不是string，而是uint8

func isIsomorphic(s string, t string) bool {
    for i := 0; i < len(s); i++ {
        if strings.Index(s[i+1:], s[i:i+1]) != strings.Index(t[i+1:], t[i:i+1]) {
            return false
        }
    }
    return true
}

Runtime: 0 ms, faster than 100.00% of Go online submissions forIsomorphic Strings.

Memory Usage: 2.7 MB, less than 100.00% of Go online submissions for Isomorphic Strings.