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.

Solution

Bit Manipulation

public class Solution {
    public char findTheDifference(String s, String t) {
        int len = t.length();
        char c = t.charAt(len - 1);
        for (int i = 0; i < len - 1; i++) {
            c ^= s.charAt(i) ^ t.charAt(i);
        }
        return c;
    }
}

Calculate difference of chars

public class Solution {
    public char findTheDifference(String s, String t) {
        int len = t.length(), c = t.charAt(len - 1);
        for (int i = 0; i < len - 1; i++) {
            c += t.charAt(i) - s.charAt(i);
        }
        return (char) c;
    }
}

Analysis

We have two different approaches to this problem, but their ideas are similar
t has only one more char than s, so we inti the result c = t.charAt(len - 1)
Then we loop through the characters in s, and find the difference
In Bit Manipulation solution, we use XOR to get difference
In the second solution, we simply calculate the difference of each char
At the end, return the remain difference character

Note:

• char also has XOR operation
• We can put iterative XOR in same line: c ^= s.charAt(i) ^ t.charAt(i);
• char can be converted to int without casting, but int to char casting needs to be explicit