LeetCode算法题-Find the Difference（Java实现-五种解法）

佚名 5年前 (2018-12-27) 算法 1143人围观抢沙发百度已收录

这是悦乐书的第214次更新，第227篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第82题（顺位题号是389）。给定两个字符串s和t，它们只包含小写字母。字符串t由随机混洗字符串s生成，然后在随机位置再添加一个字母。找到t中添加的字母。例如：

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

输入：s =“abcd”, t =“abcde”
输出：'e'

说明：'e'是添加的字母。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

因为限定字符串都是小写字母，可以借助一个26长度的数组，将t中的字符出现次数记录下来，然后再去遍历s的字符，只要有对应的就做减法，最后再去找数组中为1的元素的索引，将其和字符a相加，就是t中添加的字母。

此解法的时间复杂度是O(n)，空间复杂度是O(1)。

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

03 第二种解法

还是使用长度26的数组，将s中出现的字符及次数记录下来，再去遍历t的字符，同时对其对应数组中的元素做自减，如果自减后小于0，即表示当前字符没有在s中出现过，此字符就是t中添加的字母。

此解法的时间复杂度是O(n)，空间复杂度是O(1)。

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

04 第三种解法

使用异或位运算，其规则是两边的对应位不同时，取1，否则取0。两个相同的数做异或运算时，运算结果是0。0和一个非0的数做异或运算时，运算结果是那个非0的数。将s和t中的所有字符做异或运算，最后的运算结果就是多出来的那个字符。

此解法的时间复杂度是O(n)，空间复杂度是O(1)。

public char findTheDifference3(String s, String t) {
    int ch = 0;
    for (int i=0; i<s.length(); i++) {
        ch = ch^s.charAt(i);
    }
    for (int j=0; j<t.length(); j++) {
        ch = ch^t.charAt(j);
    }
    return (char)ch;
}

05 第四种解法

此解法思路和第三种解法一样，只是将两次循环合并到一次循环中去了。

此解法的时间复杂度是O(n)，空间复杂度是O(1)。

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

06 第五种解法

既然可以做异或运算，那么也可以尝试做加减运算，用t中所有字符的和减去s中所有字符的和，剩下的差就是t中多出的字母。

此解法的时间复杂度是O(n)，空间复杂度是O(1)。

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