FindTheDifference [source code]

public class FindTheDifference {
    public char findTheDifference(String s, String t) {
        if (s.length() == 0) return t.charAt(0);
        char[] s_letters = s.toCharArray(), t_letters = t.toCharArray();
        char res1 = s_letters[0], res2 = t_letters[0];
        for (int i = 1; i < s_letters.length; i++) res1 ^= s_letters[i];
        for (int i = 1; i < t_letters.length; i++) res2 ^= t_letters[i];
        return (char) (res1 ^ res2);
    }
}

这个问题刚开始拿到的时候有一个陷阱, 就是这个added letter未必就不在 s 里面;

那么暴力做法其实很简单, 一个 hashtable 或者一个 array(因为总共就26个字母), 统计#occurrence in s, 然后统计 t 的, 然后对比一下就行了;

这个问题跟之前做过的 SingleNumber 非常类似, 可以提炼出来的规律是, pair duplicate removal的问题, 这个问题可以用 xor 来完成;

速度是6ms, 90%, 应该是最优解了;

这个是实际的最优解(5ms), 就是代码精简了一些:

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

Problem 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.
Subscribe to see which companies asked this question.

Hide Tags Hash Table Bit Manipulation
Hide Similar Problems (E) Single Number