leetcode 389. Find the Difference-蒲公英云

leetcode 389. Find the Difference

一、问题描述

二、代码实现

1、桶排序

2、异或法

3、求和法

https://leetcode.com/problems/find-the-difference/

给定两个字符串，其中一个字符串是在另一个字符串的任意位置添加一个字母得到的，求这个字母

一、问题描述

测试用例：

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

字符串的元素均为小写字母

二、代码实现

1、桶排序

class Solution {
    //数组
    public char findTheDifference2(String s, String t) {
        int[] count = new int[26];  //HashMap, Array, Bits
        for (int i=0; i<s.length(); i++) {
            count[s.charAt(i) - 'a'] ++;
        }
        for (int i=0; i<t.length(); i++) {
            count[t.charAt(i) - 'a'] --;
            if (count[t.charAt(i)-'a'] == -1) {
                return t.charAt(i);
            }
        }
        return ' ';
    }
    //HashMap
    public char findTheDifference1(String s, String t) {
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i=0; i<s.length(); i++) {
            char ch = s.charAt(i);
            map.put(ch, map.getOrDefault(ch, 0)+1);
        }
        for (int i=0; i<t.length(); i++) {
            char ch = t.charAt(i);
            if (!map.containsKey(ch)) {
                return ch;
            } else {
                if (map.get(ch) == 1) {
                    map.remove(ch);
                } else {
                    map.put(ch, map.get(ch)-1);
                }
            }
        }
        return ' ';
    }
}

2、异或法

class Solution {
    public char findTheDifference3(String s, String t) {
        char ret = t.charAt(t.length()-1);
        for (int i=0; i<s.length(); i++) {
            ret ^= s.charAt(i) ^ t.charAt(i); //c ^= s.chartAt(i); 等同于 c = (char)((int)c ^ (int)s.charAt(i));
        }
        return ret;
    }
}

3、求和法

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