389. Find the Difference

題目敘述

You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

Example 1:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:

Input: s = "", t = "y"
Output: "y"

Constraints:

• 0 <= s.length <= 1000
• t.length == s.length + 1
• s and t consist of lowercase English letters.

題目翻譯

會給兩個字串變數 s 和 t，其中 t 是由 s 和一個隨機的字串插入到隨機的位置所組成的。要找出是哪個字母。

解法解析

這題主要就是可以使用最多三個，最少一個迴圈來處理。最主要的判斷是在最後的一個迴圈，在其中有許多不同的判斷方式，常見的會有：比較 index、比較字母的數量、比較兩個字母的 ASCII Code、Bit operator

比較 Index 的方式，可以參考 Swift 的範例。比較字母的數量，參考 Python count 的範例，我覺得是最好理解的解法。ASCII Code 的話，因為不同的字母會是不同的數值，所以 s 和 t 加總後相減就是多出來的字母，這個解法也是滿好懂的，可以參考 Kotlin 的範例。最後的 Bit operator 的作法是比較需要思考的。

依照 XOR 的特性

0 ^ 0 = 0
0 ^ 1 = 1
1 ^ 0 = 1
1 ^ 1 = 0

所以同字母的最後會相消，所以最後留下來的數值就會是多插入的字母

程式範例

Go

func findTheDifference(s string, t string) byte {
    ht := make(map[byte]int, 0)
    for _, ch := range []byte(t) {
        ht[ch]++
    }

    for _, ch := range []byte(s) {
        ht[ch]--
    }

    var result byte
    var count int
    for result, count = range ht {
        if count > 0 {
            break
        }
    }

    return result
}

JavaScript

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function (s, t) {
    let c = {};
    for (const ch of s) {
        c[ch] = (c[ch] || 0) + 1;
    }

    for (const ch of t) {
        if (c[ch]) {
            c[ch] = c[ch] - 1;
        } else {
            return ch;
        }
    }
};

Kotlin

class Solution {
    fun findTheDifference(s: String, t: String): Char {
        val firstSum = s.toCharArray().sumBy { it.toInt() }
        val secondSum = t.toCharArray().sumBy { it.toInt() }
        return (secondSum - firstSum).toChar()
    }
}

Python

Bit

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:

        # Initialize ch with 0, because 0 ^ X = X
        # 0 when XORed with any bit would not change the bits value.
        ch = 0

        # XOR all the characters of both s and t.
        for char_ in s:
            ch ^= ord(char_)

        for char_ in t:
            ch ^= ord(char_)

        # What is left after XORing everything is the difference.
        return chr(ch)

Set

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        for i in set(t):
            if s.count(i) != t.count(i):
                return i

Count

from collections import Counter


class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        # Prepare a counter for string s.
        # This holds the characters as keys and respective frequency as value.
        counter_s = Counter(s)

        # Iterate through string t and find the character which is not in s.
        for ch in t:
            if ch not in counter_s or counter_s[ch] == 0:
                return ch
            else:
                # Once a match is found we reduce frequency left.
                # This eliminates the possibility of a false match later.
                counter_s[ch] -= 1

Swift

class Solution {
    func findTheDifference(_ s: String, _ t: String) -> Character {
        var t = t
        for ch in s {
            if t.contains(ch), let index = t.firstIndex(of: ch) {
                t.remove(at: index)
            }
        }
        return Character(t)
    }
}