LeetCode.389.Find the Difference 找出两个数组的不同

题目描述

389 Find the Difference
https://leetcode-cn.com/problems/find-the-difference/
https://leetcode.com/problems/find-the-difference/description/

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.

---

解题过程

看到这道题就在想怎么用巧妙的方法来做。
想过用集合求差来做，但需要注意的一点是，t中的额外字符并不一定不在s中，也就是有可能s=”abc”,t=”abcc”，所以将s和t转换为集合求差集是错的。
然后受到题干中的只包含小写字母启发，发现可以将字符转换为int整型来进行数值计算，t中所有字符ascii码值之和减去s中所有字符ascii码值之和，就是t中多出来的字符。
代码如下：

class Solution {
    //集合ASC||码值之差
    public char findTheDifference(String s, String t) {
        char[] schar = s.toCharArray();
        char[] tchar = t.toCharArray();
        int tSum=0;
        for(char c : tchar){ //t中字符ascii码值之和
            tSum += c;
        }
        for(char c : schar){ //减去s中字符ascii码值之和
            tSum -= c;
        }
        return (char)tSum;
    }
}

耗时6ms。
通过后看Discuss，发现我的思路的的确不错，但可以优化，因为t串的长度是s串长度+1，所以直接一次循环即可，可以考虑如下代码：

public char findTheDifference(String s, String t) {
    int charCode = t.charAt(s.length());
    // Iterate through both strings and char codes
    for (int i = 0; i < s.length(); ++i) {
          charCode = charCode - (int)s.charAt(i) +(int)t.charAt(i);
    }
    return (char)charCode;
}

但这个代码并不快，因为它没有先转为char数组，每次都调用Java字符串的charAt()方法大大增加了开销，耗时10ms，我原来的代码遍历2遍数组都比它快。

最快的5ms的代码是用异或位运算：

class Solution {
    public char findTheDifference(String s, String t) {
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        char result = 0;
        int len = a.length;
        for(int i = 0;i<len;i++)
        {
            result = (char)(result^a[i]^b[i]);
        }
        return (char)(result^b[len]);
    }
}

我没想到这个，刚刚才做了136 Single Number就忘了。

还有一种方法，巧用数组下标，如下：

class Solution {
    public char findTheDifference(String s, String t) {
    for (int i = 0; i < 26; i++) alpha[i] = 0;
    for (char c : s.toCharArray())
        alpha[ c - 'a' ]++;

    for (char c : t.toCharArray()) {
      //could do decrement first, then check but yeah
        if (--alpha[c - 'a'] < 0)
            return c;
    }

    return 0;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_389_FindTheDifference.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_389_FindTheDifference.java

---