LeetCode关于找不同的解法

谁借莪１个温暖的怀抱￠ 2022-05-31 13:59 133阅读 0赞

第一次去LeetCode上写代码，果然自己的算法能力需要多多练习了。

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*，它们只包含小写字母。

字符串*t*由随机洗牌字符串*s*生成，然后在随机位置添加一个字母。

找到在*t*中添加的字母。

有个比较简单的思路就是将字符串都转化为char类型的数组，然后一一比对，发现不同的就是那个后来加入的字符串，在这之前一定要先对字符串数组进行整理，不然的话是不能进行比较的

代码如下

char [] s_arr=s.toCharArray();//将字符串转化为char类型数组
    		char[] t_arr=t.toCharArray();
    		Arrays.sort(s_arr);//对字符串进行整理
    		Arrays.sort(t_arr);
    		for(int i=0;i<s_arr.length;i++){
    			if(s_arr[i]!=t_arr[i]){
    				return t_arr[i];
    			}else continue;
    		}
    		return t_arr[t_arr.length-1];

但是还有一个更好的解决方法就是使用XOR（即异或操作），将两个字符串中所有的字符进行“异或”操作，最后剩下的那个字符就是我们要的结果，这是因为在“异或”过程中，两个相同字符会变成0，所以“异或”到最后就等价于0和目标字符进行“异或”，结果还是目标字符，直接输出即可，代码如下：

public char findTheDifference_B(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;  
    }

原文 [：http://blog.csdn.net/zsy112371/article/details/52355075][http_blog.csdn.net_zsy112371_article_details_52355075]

[http_blog.csdn.net_zsy112371_article_details_52355075]: http://blog.csdn.net/zsy112371/article/details/52355075