Leetcode-389- 找不同

题目描述

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

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

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

示例 1：

输入：s = "abcd", t = "abcde"
输出："e"
解释：'e' 是那个被添加的字母。

示例 2：

输入：s = "", t = "y"
输出："y"

示例 3：

输入：s = "a", t = "aa"
输出："a"

示例 4：

输入：s = "ae", t = "aea"
输出："a"

思路1 ： 求和

• 将字符串s中的每个字符的ASCII码进行求和，得到As
• 将字符串t中的每个字符的ASCII码进行求和，得到At
• 两者差值At - As 即代表了被添加了的字符

class Solution {
    public char findTheDifference(String s, String t) {
        int as = 0, at = 0;
        for (int i = 0; i < s.length(); ++i) {
            as += s.charAt(i);
        }
        for (int i = 0; i < t.length(); ++i) {
            at += t.charAt(i);
        }
        return (char) (at - as);
    }
}

复杂度分析

• 时间复杂度 ： O(N）
• 空间复杂度 ： O(1)

class Solution {
    public char findTheDifference(String s, String t) {
        char[] as = s.toCharArray();
        char[] at = t.toCharArray();
        int sum1 = 0;
        int sum2 = 0;

        // 1. 计算字符串s的ASCII码和
        for(int i = 0;i < as.length;i++){
            sum1 += as[i];
        }

        // 2.计算字符串t的ASCII码和
        for(int i = 0;i < at.length;i++){
            sum2 += at[i];
        }

        // 3. 差值为结果
        return (char)(sum2 - sum1);
    }
}

复杂度分析

• 时间复杂度 ： O(N）
• 空间复杂度 ： O(N)

思路2 ： 计数

• 首先遍历字符串 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 ' ';
    }
}

复杂度分析

• 时间复杂度 ： O(N)
• 空间复杂度 ： O(1)

打赏