Open
Description
给定两个字符串 s 和 t,它们只包含小写字母。
字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。
请找出在 t 中被添加的字母。
示例:
输入:
s = "abcd"
t = "abcde"
输出:
e
解释:
'e' 是那个被添加的字母。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-the-difference
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
思路
查找 map
分别为 s
和 t
记录一个字符出现数量的 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)
}