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)
    }
}

LeetCode Solution, Easy, 389. Find the Difference

Comments

LeetCode Solution

More from this blog

如何開始入門軟體工程領域 - 名詞解釋（長期更新）

我的 MacBook Pro (Apple Silicon) 設定

ChatGPT 下的發展預想

一些覺得有用的工具蒐藏

LeetCode Solution, Medium, 607. Sales Person

389. Find the Difference

題目敘述

題目翻譯

解法解析

程式範例

Go

JavaScript

Kotlin

Python

Bit

Set

Count

Swift

Command Palette

Comments

LeetCode Solution

More from this blog

389. Find the Difference

題目敘述

題目翻譯

解法解析

程式範例

Go

JavaScript

Kotlin

Python

Bit

Set

Count

Swift