问题描述
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:
Input:
s = “abcd”
t = “abcde”
Output: e
Explanation: ‘e’ is the letter that was added.
方法一
解题思路:
直接简单暴力查找, 算法复杂度O(n^2).
代码实现:
private static char findTheDifference(String s, String t) {
char[] chars1 = s.toCharArray();
char[] chars2 = t.toCharArray();
for (int i = 0; i < chars2.length; i++) {
boolean exist = false;
for (int j = 0; j < chars1.length; j++) {
if (chars2[i] == chars1[j]){
exist = true;
break;
}
}
if (!exist) return chars2[i];
}
throw new IllegalArgumentException("no other letter was added.");
}
方法二
将原字符串转换为字符List, 然后利用其contains方法进行遍历判断, 算法复杂度:O(n)
代码实现:
private char findTheDifference(String s, String t){
Character[] chars = new Character[s.length()];
//转换为Character数组
for (int i = 0; i < s.length(); i++) {
chars[i] = s.charAt(i);
}
//转换为Character List
List charList = Arrays.asList(chars);
//依次变量判断
for (int i = 0; i < t.length(); i++) {
if (!charList.contains(t.charAt(i))){
return t.charAt(i);
}
}
throw new IllegalArgumentException("no other letter was added.");
}
方法三
解决思路:
方法一简单粗暴, 方法二使用java api 比较冗余低效, 继续优化, 因为两个字符串中, 其中一个字符串只比另一个字符串多了一个字符, 其他都相同, 因此我们可以利用一条性质: 任何数异或自己都为0, 那么这两个字符串的字符依次进行异或处理, 最后剩下的就是多出来的字符了.
代码实现:
private char findTheDifference(String s, String t){
char answer = 0;
for (int i = 0; i < s.length(); i++) {
answer ^= s.charAt(i);
}
for (int i = 0; i < t.length(); i++) {
answer ^= t.charAt(i);
}
return answer;
}
###总结
简单问题, 细致分析, 结果便是别开生面的惊喜.
