算法复习-化归思想

文章灵感来自 leetcode 一篇题解全网耗时最低解题思路:化归(48ms，100%)

简单来说就是将数据格式进行转后，然后进行下一步操作，比如这道题205.同构字符串

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

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

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

示例 1:

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

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

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

经过对题目的分析，判断两个字符串是否是「同构」需要判断 s 和 t 每个位置上的字符是否都一一对应，即 s 的任意一个字符被 t 中唯一的字符对应，同时 t 的任意一个字符被 s 中唯一的字符对应。这也被称为「双射」的关系。传统的做法是在遍历时存储两个映射，然后对比映射关系是否一致:

var isIsomorphic = function (s, t) {
  if (s.length !== t.length) {
    return false;
  }

  if (s.length < 2) {
    return true;
  }

  const map = new Map();
  const set = new Set();
  for (let i = 0; i < s.length; i++) {
    if (map.has(s[i])) {
      if (map.get(s[i]) !== t[i]) return false;
    } else {
      if (set.has(t[i])) return false;
      map.set(s[i], t[i]);
      set.add(t[i]);
    }
  }
  return true;
};

但这种写法有些许难懂，我们可以用另一种方法来判断两个字符串是否「同构」-即将字符串转换为相同的表示结构再进行对比

egg -> 122
abb -> 122

这样，我们只需要对比转换后的结果 122 和 122 是否一致就好了

var isIsomorphic = function (s, t) {
  if (s.length !== t.length) {
    return false;
  }
  if (s === t) {
    return true;
  }

  const p = (s) => {
    const m = {};
    return s.split("").reduce((acc, cur, index) => {
      if (!m[cur]) {
        m[cur] = index + 1;
      }
      return `${acc}${m[cur]}`;
    }, "");
  };

  return p(s) === p(t);
};

这种方法还可以在以下题目中使用

290.单词规律

通过将 pattern 和 s 分别转换为同样的格式，对别结果即可

const parse = (words) => {
  const r = {};
  return words.reduce((acc, cur, index) => {
    if (!r[cur]) {
      r[cur] = index + 1;
    }
    return `${acc}${r[cur]}`;
  }, []);
};

const r1 = parse(pattern.split(""));
const r2 = parse(s.split(" ").map((w) => `_${w}`));

return r1 === r2;