[Java] Leetcode 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.

解答1

class Solution {
    public char findTheDifference(String s, String t) {
        char c = 0;
        for(char cs : s.toCharArray()) c ^= cs;
        for(char ct : t.toCharArray()) c ^= ct;
        return c;
    }
}

该解法使用了异或运算的性质。异或运算(XOR)是一种按位运算,对应位相同为0,不同为1。并且,对同一个数进行两次异或运算会得到原来的数。 这里的代码遍历字符串 s 和 t 中的每个字符,将字符的 ASCII 码进行异或操作,最后剩下的字符就是在 t 中额外添加的那个字符。由于对同一个数进行两次异或运算会得到原来的数,因此在循环过程中,相同的字符会互相抵消,最终剩下的就是那个额外添加的字符。 让我们逐步分析代码:

public class Solution {
    public char findTheDifference(String s, String t) {
        char c = 0; // 初始值设为0
        for (char cs : s.toCharArray()) c ^= cs; // 对字符串 s 中的每个字符进行异或运算
        for (char ct : t.toCharArray()) c ^= ct; // 对字符串 t 中的每个字符进行异或运算
        return c; // 返回最终结果
    }
}

例如,如果 s = "abcd"t = "abcde",那么:

  1. 对于字符串 s,ASCII 码为 'a' ^ 'b' ^ 'c' ^ 'd'

  2. 对于字符串 t,ASCII 码为 'a' ^ 'b' ^ 'c' ^ 'd' ^ 'e'

  3. 最终的结果为 'e'

这个解法利用了异或运算的性质,使得相同的字符在异或过程中被抵消,最终剩下的就是额外添加的字符。