389-find-the-difference

Question

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.

Thought Process

1. Hash Table
   1. Use count array to store the frequency of character, increase for string s and decrease t
   2. Loop from letter a to z, the first encounter of count = 1 is our answer
   3. Time complexity O(n)
   4. Space complexity O(n) or O(1)
2. Sum
   1. Similar to above, we add the character from s and deduct the character from t
   2. The final sum is the character
   3. Time complexity O(n)
   4. Space complexity O(1)
3. XOR
   1. XOR all the character
   2. Time complexity O(n)
   3. Space complexity O(1)

Solution

class Solution {
    public char findTheDifference(String s, String t) {
        int[] count = new int[26];
        int n = s.length();
        for (int i = 0; i < n; i++) {
            count[s.charAt(i) - 'a']--;
            count[t.charAt(i) - 'a']++;
        }
        count[t.charAt(n) - 'a']++;
        int c = 0;
        for (int i = 0; i < 26; i++) {
            if (count[i] == 1) {
                c = i + 'a';
                break;
            }
        }
        return (char) c;
    }
}

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

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

Additional