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.
一開始，我嘗試用 hashMap 的方法來做此題崎岂，但是 hashmap 的 key 是唯一的捆毫，而此題會(huì)的輸入 string 會(huì)包括相同的字符，因此不使用 hashmap冲甘。
于是绩卤，我想到了 CS180 和 CS240 都提到的數(shù)字符串里每個(gè)支付的方法，建立一個(gè)和 ASCII 表一樣大的整數(shù)數(shù)組江醇，以字符串的值作為下標(biāo)記錄每個(gè)字符串出現(xiàn)的次數(shù)濒憋，第一遍過 input的時(shí)候++，過一遍 target 的時(shí)候--陶夜，就能得到多出來的字符是哪個(gè)了凛驮。
My solution:
public class Solution {
public char findTheDifference(String s, String t) {
int[] alphabet = new int[256];
for(int i = 0; i < s.length(); i++) {
alphabet[s.charAt(i)]++;
}
for (int i = 0; i < t.length(); i++) {
alphabet[t.charAt(i)]--;
}
for (int i = 0; i < alphabet.length; i++){
if(alphabet[i] == -1) {
return (char)i;
}
}
return '0';
}
}
后來看到別人的方法，才恍然大悟条辟，這個(gè)題目其實(shí)和之前做的 hamming distance 并無本質(zhì)區(qū)別黔夭，hamming distance 是計(jì)算兩個(gè)整數(shù)之間不同的 bit 的數(shù)目，而本題是計(jì)算兩個(gè)字符串中多出來的一個(gè)字符羽嫡。
因此本姥，在這里，我們完全可以再次前幾個(gè) blog 里提到的關(guān)于異或的重要性質(zhì)：即 A ^ A = 0杭棵。
public char findTheDifference(String s, String t) {
char c = 0;
for (int i = 0; i < s.length(); ++i) {
c ^= s.charAt(i);
}
for (int i = 0; i < t.length(); ++i) {
c ^= t.charAt(i);
}
return c;
}
maybe a more elegant version:
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;
}
