[LeetCode] 389. Find the Difference

Given two strings s and t which consist of only lowercase letters.

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

Find the letter that was added in t.

Example:

Input:
s = "abcd"
t = "abcde"

Output:
e

Explanation:
'e' is the letter that was added.

找不同。

题意是给了两个string S和T，它们只包含小写字母。其中T是S 随机重排后又额外加了一个character。找出这个额外的character。

思路还是用异或XOR，两边按char做XOR。相同的char做XOR为0，如果S和T一模一样，最后的结果会是0；在T中额外的char异或0的时候，会得到它本身。代码如下，

 1 /**
 2  * @param {string} s
 3  * @param {string} t
 4  * @return {character}
 5  */
 6 var findTheDifference = function(s, t) {
 7     let ss = s.split('').sort();
 8     let tt = t.split('').sort();
 9     let i;
10     for (i = 0; i < ss.length; i++) {
11         if (ss[i] !== tt[i]) {
12             return tt[i];
13         }
14     }
15     return tt[i];
16 };

2020年1月2日更新

之前的做法根本不是位运算，而是简单的数组排序一一比较。位运算代码如下

时间O(n) - number of characters

空间O(1)

JavaScript实现

 1 /**
 2  * @param {string} s
 3  * @param {string} t
 4  * @return {character}
 5  */
 6 var findTheDifference = function (s, t) {
 7     let c = t.charCodeAt(t.length - 1);
 8     for (let i = 0; i < s.length; i++) {
 9         c ^= s.charCodeAt(i);
10         c ^= t.charCodeAt(i);
11     }
12     return String.fromCharCode(c);
13 };

Java实现

 1 class Solution {
 2     public char findTheDifference(String s, String t) {
 3         char c = t.charAt(t.length() - 1);
 4         for (int i = 0; i < s.length(); i++) {
 5             c ^= s.charAt(i);
 6             c ^= t.charAt(i);
 7         }
 8         return c;
 9     }
10 }

LeetCode 题目总结