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.
本题最直观的思路为排序后对s和t逐位进行比较。故得以下代码：
1 class Solution 2 { 3 public: 4 char findTheDifference(string s, string t) 5 { 6 sort(s.begin(), s.end()); 7 sort(t.begin(), t.end()); 8 for(int i = 0; i < s.size(); i++) 9 { 10 if(s[i] == t[i]) 11 { 12 continue; 13 } 14 else 15 { 16 return t[i]; 17 } 18 } 19 return t[t.size() - 1]; 20 } 21 };
由于排序复杂度过高，于是查询别的解法发现，可以建立一个字母表，s出现一次字母表对应位置+1，t中出现一次对应位置-1。那么只在t中出现的字母的位置为-1。代码如下：
1 public char findTheDifference(String s, String t) { 2 if(s == null || s.length() == 0) 3 return t.charAt(0); 4 int[] letters = new int[26]; 5 for(int i = 0; i < s.length(); i++){ 6 int sPosition = s.charAt(i) - ‘a‘; 7 int tPosition = t.charAt(i) - ‘a‘; 8 letters[sPosition]++; 9 letters[tPosition]--; 10 } 11 int tPosition = t.charAt(t.length()-1) - ‘a‘; 12 letters[tPosition]--; 13 char res = ‘a‘; 14 for(int i = 0; i < letters.length; i++){ 15 if(letters[i] == -1){ 16 res+= i; 17 break; 18 } 19 } 20 return res; 21 }
LeetCode 389. Find the Difference
原文：http://www.cnblogs.com/yrwang/p/6082238.html