当前位置 : 首页 » 文章分类 :  算法  »  LeetCode.389.Find the Difference

LeetCode.389.Find the Difference


题目描述

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.

解题过程

看到这道题就在想怎么用巧妙的方法来做。
想过用集合求差来做,但需要注意的一点是,t中的额外字符并不一定不在s中,也就是有可能s=”abc”,t=”abcc”,所以将s和t转换为集合求差集是错的。
然后受到题干中的只包含小写字母启发,发现可以将字符转换为int整型来进行数值计算,t中所有字符ascii码值之和减去s中所有字符ascii码值之和,就是t中多出来的字符
代码如下:

class Solution {
    //集合ASC||码值之差
    public char findTheDifference(String s, String t) {
        char[] schar = s.toCharArray();
        char[] tchar = t.toCharArray();
        int tSum=0;
        for(char c : tchar){ //t中字符ascii码值之和
            tSum += c;
        }
        for(char c : schar){ //减去s中字符ascii码值之和
            tSum -= c;
        }
        return (char)tSum;
    }
}

耗时6ms。
通过后看Discuss,发现我的思路的的确不错,但可以优化,因为t串的长度是s串长度+1,所以直接一次循环即可,可以考虑如下代码:

public char findTheDifference(String s, String t) {
    int charCode = t.charAt(s.length());
    // Iterate through both strings and char codes
    for (int i = 0; i < s.length(); ++i) {
          charCode = charCode - (int)s.charAt(i) +(int)t.charAt(i);
    }
    return (char)charCode;
}

但这个代码并不快,因为它没有先转为char数组,每次都调用Java字符串的charAt()方法大大增加了开销,耗时10ms,我原来的代码遍历2遍数组都比它快。

最快的5ms的代码是用异或位运算

class Solution {
    public char findTheDifference(String s, String t) {
        char[] a = s.toCharArray();
        char[] b = t.toCharArray();
        char result = 0;
        int len = a.length;
        for(int i = 0;i<len;i++)
        {
            result = (char)(result^a[i]^b[i]);
        }
        return (char)(result^b[len]);
    }
}

我没想到这个,刚刚才做了136 Single Number就忘了。

还有一种方法,巧用数组下标,如下:

class Solution {
    public char findTheDifference(String s, String t) {
    for (int i = 0; i < 26; i++) alpha[i] = 0;
    for (char c : s.toCharArray())
        alpha[ c - 'a' ]++;

    for (char c : t.toCharArray()) {
      //could do decrement first, then check but yeah
        if (--alpha[c - 'a'] < 0)
            return c;
    }

    return 0;
    }
}

GitHub代码


上一篇 LeetCode.349.Intersection of Two Arrays

下一篇 LeetCode.543.Diameter of Binary Tree

阅读
589
阅读预计3分钟
创建日期 2018-01-24
修改日期 2018-01-25
类别
百度推荐