Question

2628. 完全相等的 JSON 字符串

English Version

题目描述

给定两个对象 o1 和 o2 ，请你检查它们是否 完全相等 。

对于两个 完全相等 的对象，必须满足以下条件：

• 如果两个值都是原始类型，它们通过了 === 等式检查，则认为这两个值是 完全相等 的。
• 如果两个值都是数组，在它们具有相同元素且顺序相同，并且每个元素在这些条件下也 完全相等 时，认为这两个值是 完全相等 的。
• 如果两个值都是对象，在它们具有相同键，并且每个键关联的值在这些条件下也 完全相等 时，认为这两个值是 完全相等 的。

你可以假设这两个对象都是 JSON.parse 的输出。换句话说，它们是有效的 JSON 。

请你在不使用 lodash 的 _.isEqual() 函数的前提下解决这个问题。

 

示例 1：

输入：o1 = {"x":1,"y":2}, o2 = {"x":1,"y":2}
输出：true
输入：键和值完全匹配。

示例 2：

输入：o1 = {"y":2,"x":1}, o2 = {"x":1,"y":2}
输出：true
解释：尽管键的顺序不同，但它们仍然完全匹配。

示例 3：

输入：o1 = {"x":null,"L":[1,2,3]}, o2 = {"x":null,"L":["1","2","3"]}
输出：false
解释：数字数组不同于字符串数组。

示例 4：

输入：o1 = true, o2 = false
输出：false
解释：true !== false

 

提示：

• 1 <= JSON.stringify(o1).length <= 105
• 1 <= JSON.stringify(o2).length <= 105
• maxNestingDepth <= 1000

解法

方法一：递归

我们先判断 o1 是否为空，或者 o1 是否非对象类型。如果是，则直接返回 o1 和 o2 是否相等。

否则，我们判断 o1 和 o2 的类型是否相同。如果不同，则返回 false。

接下来，我们判断 o1 和 o2 是否都是数组。如果不是，则返回 false。

如果是数组，则判断两个数组的长度是否相同。如果不同，则返回 false。否则，我们遍历两个数组对应位置的元素，递归调用 areDeeplyEqual 函数，判断两个元素是否相等。如果有一个元素不相等，则返回 false。否则，返回 true。

如果 o1 和 o2 都不是数组，则判断两个对象的键的个数是否相同。如果不同，则返回 false。否则，我们遍历 o1 的所有键，递归调用 areDeeplyEqual 函数，判断两个键对应的值是否相等。如果有一个键对应的值不相等，则返回 false。否则，返回 true。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为 o1 和 o2 的长度。

function areDeeplyEqual(o1: any, o2: any): boolean {
  if (o1 === null || typeof o1 !== 'object') {
    return o1 === o2;
  }
  if (typeof o1 !== typeof o2) {
    return false;
  }
  if (Array.isArray(o1) !== Array.isArray(o2)) {
    return false;
  }
  if (Array.isArray(o1)) {
    if (o1.length !== o2.length) {
      return false;
    }
    for (let i = 0; i < o1.length; i++) {
      if (!areDeeplyEqual(o1[i], o2[i])) {
        return false;
      }
    }
    return true;
  } else {
    const keys1 = Object.keys(o1);
    const keys2 = Object.keys(o2);
    if (keys1.length !== keys2.length) {
      return false;
    }
    for (const key of keys1) {
      if (!areDeeplyEqual(o1[key], o2[key])) {
        return false;
      }
    }
    return true;
  }
}