Question

Formatted question description: https://leetcode.ca/all/389.html

You are given two strings s and t.

String t is generated by random shuffling string s and then add one more letter at a random position.

Return the letter that was added to t.

Example 1:

Input: s = "abcd", t = "abcde"
Output: "e"
Explanation: 'e' is the letter that was added.

Example 2:

Input: s = "", t = "y"
Output: "y"

Constraints:

0 <= s.length <= 1000
t.length == s.length + 1
s and t consist of lowercase English letters.

Algorithm

Use a hash table to establish a mapping between characters and numbers. If a mapping value is less than 0 when traversing t, then return the character.

You can also use addition and subtraction directly, the same character minus one plus also cancels out, the rest is the character added later.

Also, Bit Manipulation by using the property of XOR, the same bit returns 0, so that the same characters are cancelled out, and the rest is the character added later

Code

public class Find_the_Difference {

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

    class Solution_plusMinus {
        public char findTheDifference(String s, String t) {
            char res = 0;
            for (char c : s.toCharArray()) res -= c;
            for (char c : t.toCharArray()) res += c;
            return res;

        }
    }

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

############

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

// OJ: https://leetcode.com/problems/find-the-difference/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    char findTheDifference(string s, string t) {
        int cnt[26] = {};
        for (char c : s) cnt[c - 'a']++;
        for (char c : t) {
            if (--cnt[c - 'a'] < 0) return c;
        }
        return 0;
    }
};

class Solution:
    def findTheDifference(self, s: str, t: str) -> str:
        cnt = Counter(s)
        for c in t:
            cnt[c] -= 1
            if cnt[c] < 0:
                return c

############

class Solution(object):
  def findTheDifference(self, s, t):
    """
    :type s: str
    :type t: str
    :rtype: str
    """
    sum1 = sum(map(ord, [c for c in s]))
    sum2 = sum(map(ord, [c for c in t]))
    return chr(sum2 - sum1)

func findTheDifference(s, t string) byte {
	cnt := [26]int{}
	for _, ch := range s {
		cnt[ch-'a']++
	}
	for i := 0; ; i++ {
		ch := t[i]
		cnt[ch-'a']--
		if cnt[ch-'a'] < 0 {
			return ch
		}
	}
}

function findTheDifference(s: string, t: string): string {
    return String.fromCharCode(
        [...t].reduce((r, v) => r + v.charCodeAt(0), 0) -
            [...s].reduce((r, v) => r + v.charCodeAt(0), 0),
    );
}

impl Solution {
    pub fn find_the_difference(s: String, t: String) -> char {
        let mut ans = 0;
        for c in s.as_bytes() {
            ans ^= c;
        }
        for c in t.as_bytes() {
            ans ^= c;
        }
        char::from(ans)
    }
}

389 - Find the Difference

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions