leetcode中如何解決找不同問題

題目鏈接

https://leetcode-cn.com/problems/find-the-difference/

題目描述

給定兩個(gè)字符串 s 和 t，它們只包含小寫字母。

字符串 t 由字符串 s 隨機(jī)重排，然后在隨機(jī)位置添加一個(gè)字母。

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

示例:

輸入：
s = "abcd"
t = "abcde"

輸出：
e

解釋：
'e' 是那個(gè)被添加的字母。

解題方案

思路

• 標(biāo)簽：哈希表

• 本題最容易想到的就是使用哈希表進(jìn)行運(yùn)算，遍歷第一個(gè)字符串標(biāo)記出現(xiàn)的字符數(shù)量，再遍歷第二個(gè)減去出現(xiàn)的數(shù)量，直到遇到為0或者原哈希表就不存在的情況

• 標(biāo)簽：異或運(yùn)算

• 除了上述方法外，會(huì)有一個(gè)更tricky的解法，就是使用字符（注意不是字符串）異或運(yùn)算，盡管并沒有降低時(shí)間復(fù)雜度，但也是一種開闊思路的解題方式

• 使用異或運(yùn)算可以解題主要因?yàn)楫惢蜻\(yùn)算有以下幾個(gè)特點(diǎn)：

• 一個(gè)數(shù)和0做XOR運(yùn)算等于本身：a⊕0 = a

• 一個(gè)數(shù)和其本身做XOR運(yùn)算等于0：a⊕a = 0

• XOR運(yùn)算滿足交換律和結(jié)合律：a⊕b⊕a = (a⊕a)⊕b = 0⊕b = b

• 故而在以上的基礎(chǔ)條件上，將所有數(shù)字按照順序做抑或運(yùn)算，最后剩下的結(jié)果即為唯一的數(shù)字

• 時(shí)間復(fù)雜度：O(m+n)，m為字符串s的長度，n為字符串t的長度

代碼

• Java版本

class Solution {
    public char findTheDifference(String s, String t) {
        char ans = t.charAt(t.length()-1);
        for(int i = 0; i < s.length(); i++) {
            ans ^= s.charAt(i);
            ans ^= t.charAt(i);
        }
        return ans;
    }
}

• JavaScript版本

JavaScript由于沒有字符位運(yùn)算所以無法使用異或運(yùn)算解法。故而使用了第一種哈希表的解法

/**
 * @param {string} s
 * @param {string} t
 * @return {character}
 */
var findTheDifference = function(s, t) {
    const map = new Map();
    for(let i = 0; i < s.length; i++) {
        const val = map.get(s[i]);
        map.set(s[i], val === undefined ? 1 : val + 1);
    }
    for(let i = 0; i < t.length; i++) {
        const val = map.get(t[i]);
        if(val === 0 || val === undefined) {
            return t[i];
        } else {
            map.set(t[i], val - 1);
        }
    }
};

畫解