leetcode#389 Find the Difference

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:

1
2
3
4
5
6
7
8
9
10
>Input:
>s = "abcd"
>t = "abcde"
>
>Output:
>e
>
>Explanation:
>'e' is the letter that was added.
>

解释

给定两个字符串s和t，都由小写字母构成。字符串t是由字符串s中的字符随机排列后，再随机添加一个字符后得到的。

要求找出添加的字符。

我的解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public char findTheDifference(String s, String t) {
        char[] sChar = s.toCharArray();
        char[] tChar = t.toCharArray();
        Arrays.sort(sChar);
        Arrays.sort(tChar);
        char res = ' ';
        for(int i = 0; i < sChar.length; i++) {
            if(sChar[i] == tChar[i]) continue;
            else {
                res = tChar[i];
                break;
            }   
        }
        if(res == ' ') res = tChar[tChar.length - 1];
        return res;
    }
}

大神解法

类似于leetcode136，只不过本题是字符串中的一个字符，leetcode136是数组中的一个数字。

解法一：位运算（BitManipulation）

两个字符串的不同只在于一个字符，所以对所有的字符进行异或运算，最后的结果就是唯一不同的字符。

1
2
3
4
5
6
7
8
9
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;
}

解法二：位运算的变形——利用字符的int表示。

两个字符串中的字符对应的int数作差，最后剩下的int对应的字符就是唯一不同的字符。

1
2
3
4
5
6
7
8
9
public char findTheDifference(String s, String t) {
        int charCode = t.charAt(s.length());
        // Iterate through both strings and char codes
        for (int i = 0; i < s.length(); ++i) {
              charCode -= (int)s.charAt(i);
              charCode += (int)t.charAt(i); 
        }
        return (char)charCode;
    }