05 August 2008
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
Input:
s = "abcd"
t = "abcde"
Output:
e
Explanation:
'e' is the letter that was added.
给一个字符串s，根据s把里面的字符都shuffle一下然后随机加一个字符然后生产t，找到刚才随机加上的字符。
首先位操作的XOR可以去掉重复，因为自己和自己异或等于0；另外也可以计算两个字符串char codes的差距，然后转换成char即可，时间O(n)，空间O(1)。
char b = ‘a’+18; //因为char本身在码表中可以用数字表示的，然后运算玩之后还是char，应该输出s
char a = ‘a’; //这个定义就是错误的。
char b = a + 18; // 这样也是错的，因为JVM运算完后不知道结果是多少，所以会提示损失精度的错误，关于一个类型变量值的问题。
XOR
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public char findTheDifference(String s, String t) {
int len = t.length();
char ch = t.charAt(len - 1);//初始化，注意长字符串t最后多出来的那位为初始值，因为下面的循环要保证每个元素都遍历到
for (int i = 0; i < len - 1; i++) {//i < len -1，短的字符串不越界
ch ^= s.charAt(i);
ch ^= t.charAt(i);
}
return ch;
}
}
XOR更好理解的做法，需要一点额外空间，两个串合在一起然后XOR，最后剩余的就是多出来的字符
1
2
3
4
5
6
7
8
9
10
class Solution {
public char findTheDifference(String s, String t) {
String merge = s + t;
char ch = 0;//初始化，这里表示ch的初始值为空格' '，P.S.，用ch != '\0'判断字符是否为空格
for (int i = 0; i < merge.length(); i++) {
ch ^= merge.charAt(i);//等于 ch = (char) (ch ^ merge.charAt(i));
}
return ch;
}
}
int和char转换的做法
1
2
3
4
5
6
7
8
9
10
11
class Solution {
public char findTheDifference(String s, String t) {
int len = s.length();
int charCode = t.charAt(len);//初始化为长的字符串最后一位，因为下面的循环要保证每个元素都遍历到
for (int i = 0; i < len; i++) {
charCode -= s.charAt(i);
charCode += t.charAt(i);
}
return (char)charCode;
}
}