LeetCode - Algorithms - 389. Find the Difference

Problem

389. Find the Difference

Java

bit manipulation

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public char findTheDifference(String s, String t) {
        char c = ' ';
        s += t;
        int x = (int) (s.charAt(0));
        for (int i = 1; i < s.length(); i++) {
            x ^= (int) (s.charAt(i));
        }
        c = (char) x;
        return c;
    }
}

Submission Detail

  • 54 / 54 test cases passed.
  • Runtime: 2 ms, faster than 49.97% of Java online submissions for Find the Difference.
  • Memory Usage: 37.4 MB, less than 50.18% of Java online submissions for Find the Difference.

bucket

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public char findTheDifference(String s, String t) {
        char c = ' ';
        final int N = 26;
        int[] a = new int[N];
        for (int i = 0; i < t.length(); i++) {
            a[t.charAt(i) - 'a']++;
        }
        for (int i = 0; i < s.length(); i++) {
            a[s.charAt(i) - 'a']--;
        }
        for (int i = 0; i < N; i++) {
            if (a[i] > 0) {
                c = (char) (i + 'a');
                break;
            }
        }
        return c;
    }
}

Submission Detail

  • 54 / 54 test cases passed.
  • Runtime: 2 ms, faster than 49.97% of Java online submissions for Find the Difference.
  • Memory Usage: 37.2 MB, less than 88.24% of Java online submissions for Find the Difference.

HashMap

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public char findTheDifference(String s, String t) {
        char r = ' ';
        Map<Character, Integer> map = new HashMap<Character, Integer>();
        char c = ' ';
        for(int i=0;i<t.length();i++) {
            c = t.charAt(i);
            if (map.containsKey(c))
                map.put(c, map.get(c)+1);
            else
                map.put(c,1);
        }
        for(int i=0;i<s.length();i++) {
            c = s.charAt(i);
            if (map.containsKey(c))
                map.put(c, map.get(c)-1);
        }
        for(Map.Entry<Character, Integer> e : map.entrySet()) {
            if (e.getValue()>0)
                r = e.getKey();
        }
        return r;
    }
}

Submission Detail

  • 54 / 54 test cases passed.
  • Runtime: 8 ms, faster than 16.46% of Java online submissions for Find the Difference.
  • Memory Usage: 37.5 MB, less than 35.41% of Java online submissions for Find the Difference.