Fe-interview: [js] 第107天 写一个方法判断给定的字符串是否同态(isomorphic)

[haizhilin2013]

第107天 写一个方法判断给定的字符串是否同态(isomorphic)

[xxf1996]

好吧，首先要知道什么是同态：

两个字符串，如果A字符串中的每一个字符都可以在B字符串中找到唯一对应，并且顺序一一对应；如果存在这样的函数，那么A和B同态。

简言之，字符串同态就是字符串拥有同样的字符结构；

function isomorphic (a, b) {
  let res = true
  if (a.length === b.length) { // 首先字符串长度肯定要一致
    let ka = {}
    let kb = {}
    res = b.split('').every((item, idx) => {
      if (!kb[item]) {
        kb[item] = a[idx] // 存放b字符串当前字符对应于a字符串中的哪个字符（映射）
      }
      return kb[item] === a[idx] // 判断b字符串当前字符对应于a字符串中的映射是否与a字符串当前索引的字符一致
    }) &&
    a.split('').every((item, idx) => {
      if (!ka[item]) {
        ka[item] = b[idx] // 存放a字符串当前字符对应于b字符串中的哪个字符（映射）
      }
      return ka[item] === b[idx] // 判断a字符串当前字符对应于b字符串中的映射是否与b字符串当前索引的字符一致
    })
  } else {
    res = false
  }

  return res
}

console.log(isomorphic('add', 'egg')) // true
console.log(isomorphic('paper', 'title')) // true
console.log(isomorphic('xyxx', 'xztt')) // false
console.log(isomorphic('aaaaa', 'abcda')) // false

感谢@HuoXiaoYe 指正错误，确实一一映射需要考虑双向的；还有通过字符差值来判断也学习到了！

[HuoXiaoYe]

@xxf1996 你好。你这样写是有问题的。举个例子，a = "aaaaa", b="abcda" , 也会判断正确。因为，你只是把b中不重复的值为键.

function isomorphic(str1, str2) {
        if(str1.length != str2.length){
                return false;
        }
        let result = true; 
        let map = {}
        for(var i=0; i<str1.length; i++){
                var code1 = str1.charCodeAt(i);
                var code2 = str2.charCodeAt(i);
                var dif = code1 - code2;
                if (map.hasOwnProperty(str1[i])) {
                        return dif === map[str1[i]]
                } else {
                        map[str1[i]] = dif
                }
        }
        return result;
}
console.log(isomorphic('add', 'egg')) // true
console.log(isomorphic('paper', 'title')) // true
console.log(isomorphic('xyxx', 'xztt')) // false
console.log(isomorphic('error', 'xxccc')) // false
console.log(isomorphic('aaaaa', 'abcda')) // false

此方法判断了每个字母 的 unicode 编码的差值是否相同。

[ghost]

@haizhilin2013
首先，isomorphic 意为同构而非同态。我找了下原题，说的是 isomorphic，因此标题中「同态」应改为「同构」。

其次，同构的定义为：
对于集合 𝐴 与 𝐵，分别有运算 ∗ 与 ∗'，
有双射 𝑓 使得 ∀ 𝑎₁, 𝑎₂ ∈ 𝐴，有 𝑓(𝑎₁ ∗ 𝑎₂) = 𝑓(𝑎₁) ∗' 𝑓(𝑎₂)，反之亦然。

先不提前面几位对于「字符串同构/同态」的定义更像是「字符串双射」，字符串和集合本身就是不同的：

• 字符串有序，而集合无序；
• 字符串可重，而集合不可重。

我怀疑所谓字符串同构只是某道特定面试题目（或许就是 LeetCode 205）中一个近似类比的定义。

另，写还是可以写的：

function isIsomorphic(a, b) {
    if (a.length !== b.length) return false
    const aToB = {}, bToA = {}
    for (let i = 0; i < a.length; i++) {
        if (a[i] in aToB && aToB[a[i]] !== b[i]) return false
        if (b[i] in bToA && bToA[b[i]] !== a[i]) return false
        if (!(b[i] in bToA) && !(a[i] in aToB)) {
            aToB[a[i]] = b[i]
            bToA[b[i]] = a[i]
        }
    }
    return true
}

考虑到这种情况可以类比为集合的双射（一一对应），这种写法使用了两个映射对象。

[forever-z-133]

有没有更浅显的概念解释呀，
比如 李文文 和 王小小 都是 ABB 类型的字符，那么就是同态么。
但看上面 isomorphic('xyxx', 'xztt') 却返回的 false，我应该是理解错了。

[haizhilin2013]

@foreverZ133 你自己转换成你理解的方式就好。一般在面试中，面试官问你知不知道什么是同态，如果你说不知道，他一般不会再继续往下问了……

[ghost]

这道题的题面表述错误。

这个题目要求的必定不是判断什么「字符串同构」，因为「同构」这个概念根本不是作用于字符串上的。这个问题真正严谨的表述是：

给定串 𝑆₁，𝑆₂ ，其中出现的字符分别有对应的字符集合 𝐶₁，𝐶₂，编写程序判断：

• 𝗅𝖾𝗇(𝑆₁) = 𝗅𝖾𝗇(𝑆₂) ，且
• 映射 𝑓(𝑆₁[𝑖]) = 𝑆₂[𝑖] (0 < 𝑖 < 𝗅𝖾𝗇(𝑆₁)) 为 𝐶₁ 至 𝐶₂ 的双射（Bijection) 。

其中 𝗅𝖾𝗇(𝑆) 为串 𝑆 的长度。

注：双射，就是使得两个集合中的元素一一对应（没有无法对应的元素，也没有多对一、一对多关系）的映射。

出这道面试题的公司应该感到羞耻。

[HuoXiaoYe]

@foreverZ133 您好，博主。可以发表一下您对这道题的看法吗。应该怎么判断呢？

[LinStan]

直接搬了leetcode205的答案。
思路是直接对比两个字符串每个字符的indexOf值是否相等，若不相等直接false

var isIsomorphic = function(s, t) {
    var ls = s.length;
    var lt = t.length;
    if(ls!=lt){return false}
    for(var i = 0;i<ls;i++)
        {
            if(s.indexOf(s[i])!=t.indexOf(t[i]))
            {return false}
        }
    return true
};

[kanjiu]

@foreverZ133 isomorphic('xyxx', 'xztt') 却返回的 false,是因为前面是abaa后面是abcc

[harmsworth]

我观察到上面有部分函数漏了一种情况
console.log(isomorphic('ab', 'aa')) // false
故添加

/**
 * 写一个方法判断给定的字符串是否同态(isomorphic)
 */
function isomorphic (str1, str2) {
  const l1 = str1.length
  const l2 = str2.length
  if (l1 !== l2) {
    return false
  }
  if (l1 === 1 && l2 === 1) {
    return true
  }
  const temp = {}
  for (let i = 0; i < l1; i++) {
    if (temp[str1[i]]) {
      return temp[str1[i]] === str2[i]
    } else {
      temp[str1[i]] = str2[i]
    }
  }
  return false
}
console.log(isomorphic('add', 'egg')) // true
console.log(isomorphic('paper', 'title')) // true
console.log(isomorphic('a', 'b')) // true
console.log(isomorphic('xyxx', 'xztt')) // false
console.log(isomorphic('error', 'xxccc')) // false
console.log(isomorphic('aaaaa', 'abcda')) // false
console.log(isomorphic('ab', 'aa')) // false