LeetCode笔记：找不同

#leetcode

问题

给定两个字符串 s 和 t，它们只包含小写字母。

字符串  t  由字符串  s  随机重排，然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

示例 1：

输入：s = "abcd", t = "abcde"

输出："e"

解释：'e' 是那个被添加的字母。

示例 2：

输入：s = "", t = "y"

输出："y"

示例 3：

输入：s = "a", t = "aa"

输出："a"

示例 4：

输入：s = "ae", t = "aea"

输出："a"

提示：

  • 0 <= s.length <= 1000
  • t.length == s.length + 1
  • s 和 t 只包含小写字母

解法一

思路：

遍历字符串 t的每一个字母，判断字母是否存在于字符串 s 中，如果存在就将 s 中的这个字母删除，否则这个字母就是 t 中被添加的字母。

代码：

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function (s, t) {
  for (const c of t) {
    if (s.indexOf(c) !== -1) {
      s = s.replace(c, "");
    } else {
      return c;
    }
  }
};

解法二

思路：

分别将字符串 s 和 t 的所有字母的 Unicode 编码加起来，再用 t 的编码数字总和减去 s 的编码数字总和，得到的结果就是 t 中被添加字母的 Unicode 编码。

代码：

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function (s, t) {
  let as = 0,
    at = 0;
  for (const cs of s) {
    as += cs.charCodeAt();
  }
  for (const ct of t) {
    at += ct.charCodeAt();
  }
  return String.fromCharCode(at - as);
};

解法三

思路：

  1. 遍历 s，统计 s 每一个字母的出现次数
  2. 遍历 t，从统计结果中扣除 t 中出现的相同的字母，一旦发现 t 比 s 字母数量多，就找到了 t 中被添加的字母

代码：

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function (s, t) {
  // 构造一个长度为26的全部填充为0的数组
  const charCount = new Array(26).fill(0);

  // 获取字母a的char code
  const aCode = "a".charCodeAt();

  // 统计s中每一个字母的出现次数
  // 比如 "acce" 统计结果为 charCount = [1, 0, 2, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  for (const cs of s) {
    charCount[cs.charCodeAt() - aCode]++;
  }

  // 从上面的统计结果中扣除t中的字母
  for (const ct of t) {
    charCount[ct.charCodeAt() - aCode]--;

    // 一旦发现超出了t中的字母数量，就找到了t中被添加的字母
    if (charCount[ct.charCodeAt() - aCode] < 0) {
      return ct;
    }
  }
};

同类型解决方案的问题请参考

LeetCode 笔记: 赎金信

解法四

思路：

运用按位异或的特性来求解

  1. 满足交换律：a ^ b ^ c <=> a ^ c ^ b
  2. 任何数和 0 异或为任何数：0 ^ n => n
  3. 相同的数异或为 0：n ^ n => 0

我们将字符 s 和 t 的所有字母的 Unicode 编码通过按位异或计算，最终结果就是 t 中被添加的字母的 Unicode 编码。

比如，s = "abcd", t = "abcde"，

0 ^ a ^ b ^ c ^ d ^ a ^ b ^ c ^ d ^ e

等价于

a ^ a ^ b ^ b ^ c ^ c ^ d ^ d ^ e

等价于

0 ^ 0 ^ 0 ^ 0 ^ e

等价于

e

代码：

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function (s, t) {
  let ret = 0;
  for (const ch of s) {
    ret ^= ch.charCodeAt();
  }
  for (const ch of t) {
    ret ^= ch.charCodeAt();
  }
  return String.fromCharCode(ret);
};

同类型解决方案的问题请参考

LeetCode 笔记: 只出现一次的数字

参考

评论