[leetcode]--389. Find the Difference

桃扇骨 2022-07-11 14:30 132阅读 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"));
    }

输出：