Skip to content

找不同-389 #109

Open
Open
@sl1673495

Description

@sl1673495

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

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

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

示例:

输入:
s = "abcd"
t = "abcde"

输出:
e

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-the-difference
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

思路

查找 map

分别为 st 记录一个字符出现数量的 map,然后遍历长度更长的那个字符串的 map,如果发现某个 key 在另一个 map 中没有出现,那么多出来的就是那个 key 的字符。

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
let findTheDifference = function (s, t) {
  let mapS = createCharsMap(s)
  let mapT = createCharsMap(t)

  let targetMap = s.length > t.length ? mapS : mapT
  let otherMap = targetMap === mapS ? mapT : mapS
  let keys = Object.keys(targetMap)
  for (let key of keys) {
    if (targetMap[key] !== otherMap[key]) {
      return key
    }
  }
}

function createCharsMap(s) {
  let map = {}
  for (let i = 0; i < s.length; i++) {
    let char = s[i]
    if (!map[char]) {
      map[char] = 1
    } else {
      map[char]++
    }
  }
  return map
}

位运算

利用 ^ 异或运算,不断的异或字符的 charCode 值,相同的值都会消除为 0,最后剩下的就是多出来的字符的 charCode 值。

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
let findTheDifference = function (s, t) {
  let rest = t.charCodeAt(t.length - 1)
  for (let i = 0; i < s.length; i++) {
    let charS = s[i]
    let charT = t[i]
    rest ^= charS.charCodeAt(0)
    rest ^= charT.charCodeAt(0)
  }
  return String.fromCharCode(rest)
}

Metadata

Metadata

Assignees

No one assigned

    Labels

    位运算待复习看题解或者做出来很艰难的,需要回顾。查找表

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions