0205. 同构字符串【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 双向映射
• 3. 🎯 s.2 - 首次出现位置索引比较

1. 📝 题目描述

• leetcode

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

如果 s 中的字符可以按某种映射关系替换得到 t，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

---

示例 1：

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

示例 2：

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

示例 3：

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

---

提示：

• 1 <= s.length <= 5 * 10^4
• t.length == s.length
• s 和 t 由任意有效的 ASCII 字符组成

2. 🎯 s.1 - 双向映射

js

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function (s, t) {
  // 如果长度不同，肯定不是同构字符串
  if (s.length !== t.length) return false

  // 建立两个映射表，确保双向一一映射
  const mapS2T = {} // s 到 t 的映射
  // {
  //   e: "a",
  //   g: "d",
  // }
  const mapT2S = {} // t 到 s 的映射
  // {
  //   a: "e",
  //   d: "g",
  // }

  for (let i = 0; i < s.length; i++) {
    const charS = s[i]
    const charT = t[i]

    // 检查 s 到 t 的映射
    if (mapS2T[charS] !== undefined) {
      // 如果已存在映射但与当前字符不一致，则不是同构字符串
      if (mapS2T[charS] !== charT) {
        return false
      }
    } else {
      // 建立新的映射
      mapS2T[charS] = charT
    }

    // 检查 t 到 s 的映射
    if (mapT2S[charT] !== undefined) {
      // 如果已存在映射但与当前字符不一致，则不是同构字符串
      if (mapT2S[charT] !== charS) {
        return false
      }
    } else {
      // 建立新的映射
      mapT2S[charT] = charS
    }
  }

  return true
}

• 时间复杂度：$O(n)$，其中 $n$ 是字符串的长度
• 空间复杂度：$O(n)$，需要存储字符映射关系
• 相似：
  • 290. 单词规律

3. 🎯 s.2 - 首次出现位置索引比较

js

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var isIsomorphic = function (s, t) {
  // 如果长度不同，肯定不是同构字符串
  if (s.length !== t.length) return false

  for (let i = 0; i < s.length; i++) {
    // 比较每个字符在各自字符串中首次出现的位置
    if (s.indexOf(s[i]) !== t.indexOf(t[i])) {
      return false
    }
  }

  return true
}

• 时间复杂度：$O(n^2)$，每次 indexOf 操作需要 $O(n)$ 时间
• 空间复杂度：$O(1)$，只使用了常数额外空间
• 核心思想：如果两个字符串同构，那么相同字符在各自字符串中首次出现的位置必然相同。