389. Find the Difference

Problem

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.

Problem Summary

Given two strings s and t, which contain only lowercase letters. String t is generated by randomly rearranging string s and then adding one letter at a random position. Find the letter that was added in t.

Solution Approach

• The problem requires finding the one character in string t that is extra compared to string s. The idea is still to use the property of XOR, X^X = 0. XOR s and t sequentially, and the final extra character is the result of the final XOR.

Code

package leetcode

func findTheDifference(s string, t string) byte {
	n, ch := len(t), t[len(t)-1]
	for i := 0; i < n-1; i++ {
		ch ^= s[i]
		ch ^= t[i]
	}
	return ch
}