亲宝软件园·资讯

展开

Go Java 算法找不同

黄丫丫 人气:0

找不同

给定两个字符串 s 和 t ,它们只包含小写字母。

字符串 t 由字符串 s 随机重排,然后在随机位置添加一个字母。

请找出在 t 中被添加的字母。

输入:s = "abcd", t = "abcde"

输出:"e"

解释:'e' 是那个被添加的字母。

输入:s = "", t = "y"

输出:"y"  

提示:

0 <= s.length <= 1000

t.length == s.length + 1

方法一:计数(Java)

首先遍历字符串 s,对其中的每个字符都将计数值加 1;然后遍历字符串 t,对其中的每个字符都将计数值减 1。

当发现某个字符计数值为负数时,说明该字符在字符串 t 中出现的次数大于在字符串 s 中出现的次数,因此该字符为被添加的字符。

class Solution {
    public char findTheDifference(String s, String t) {
        int[] cnt = new int[26];
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            cnt[ch - 'a']++;
        }
        for (int i = 0; i < t.length(); ++i) {
            char ch = t.charAt(i);
            cnt[ch - 'a']--;
            if (cnt[ch - 'a'] < 0) {
                return ch;
            }
        }
        return ' ';
    }
}

N :字符串的长度

Σ :字符集

时间复杂度:O(N)

空间复杂度:O(∣Σ∣)

方法二:求和(Go)

本方法主要是利用了ASCII码,按照字符的ASCII码进行查找不同的字符。一次遍历计算出两个字符串的ASCII总和,根据差值既可以得出插入的字符

将字符串 s 中每个字符的 ASCII 码的值求和,得到 A_s

对字符串 t 同样的方法得到 A_t

两者的差值 A_t-A_s即代表了被添加的字符。

func findTheDifference(s, t string) byte {
    sum := 0
    for _, ch := range s {
        sum -= int(ch)
    }
    for _, ch := range t {
        sum += int(ch)
    }
    return byte(sum)
}

时间复杂度:O(N)

空间复杂度:O(1)

加载全部内容

相关教程
猜你喜欢
用户评论