Question 389:

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.

z中文解释：

字符串t是由字符串s创建出来的,只是字符串t比字符串s多加了一个字母.现在是要找出这个多加的字母.

解决思路：这里提供两种解决思路：

（1）利用两层遍历找出 单独的字符：

源码如下：

/** * 思路: 循环遍历字符串s,对每一个字符,到对应的字符串t中删除,知道最后t只有一个字符. * @param s 源字符串 * @param t 加了一个字符之后的字符串 * @return 新加的这个字符串 */ public static char findTheDifference(String s, String t) { //将两个字符串转换成字符数组 char[] schar = s.toCharArray(); char[] tchar = t.toCharArray(); //遍历字符串s的字符数组,然后再字符串t中删除对应的字符,最后字符串t就会只剩下一个字符,即结果. for(char c: schar){ for(int i=0; i<tchar.length; i++){ if(c == tchar[i]){ tchar[i] = ' '; break; } } } for(char tc: tchar){ if(tc != ' '){ return tc; } } return 'f'; }

（2）利用亦或操作的特性 单独的字符：

我们都知道亦或操作有一个特点：

交换律 a^b = b^a结合律 a^b^c=a^(b^c)=(a^b)^c0^a=a 0与任何数亦或都是这个数a^a=0

所以借助这个特点，通过亦或操作^ 字节对s和t全部执行亦或操作,因为a^a结果是0,所以最后的结果是单独的那个字符

源码如下：

/** * 第二种方法:通过亦或操作^ 字节对s和t全部执行亦或操作,因为a^a结果是0,所以最后的结果是单独的那个字符 * @param s * @param t * @return */ public static char findTheDifference2(String s, String t) { int c = t.charAt(0); for(int i=0; i<s.length(); i++){ c = c ^ s.charAt(i); } //注意 i为0时已经取出了,所以这里是从1开始的. for(int i=1; i<t.length(); i++){ c = c ^ t.charAt(i); } return (char)c; }

测试案例：

public static void main(String[] args) { if('a' == 'a'){ LogUtil.log_debug("true"); } LogUtil.log_debug("result:" + findTheDifference2("aebcd", "abcdfe")); }

输出：

f