[leetcode]--389. Find the Difference

桃扇骨 2022-07-11 14:30 253阅读 0赞

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)^c
0^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"));
}