找到差异Leetcode解决方案


难度级别 易得奖学金
经常问 土砖 亚马逊 谷歌
哈希

在这个问题上,我们得到两个 字符串。 通过随机混洗第一个字符串的字符,然后在任意随机位置添加一个额外的字符来生成第二个字符串。 我们需要返回添加到第二个字符串的额外字符。 字符将始终为小写英文字母。

使用案列

a = "abcde" , b = "ebacdf"
f
a = "aaaa" , b = "aaaaa"
a

说明#1

添加到字符串的多余字符 b 是'f'作为字符串 a 不包含它。

说明#2

字符串中有4个'a'字母 有5。因此,多余的字母是“ a”。

方法(排序)

我们可以对两个字符串进行排序,然后逐个字母地对它们进行迭代,以找到它们不同的第一个位置。 第二个字符串将始终有一个 额外 特点。 因此,我们总会发现一个点,其中字符串 ab 不同。 但是,可能会出现字符串 b 排序后匹配字符串中的每个字符 a ,但最后有一个额外的角色。 我们需要处理这一特殊情况。

找到差异Leetcode解决方案

算法

  1. 对两个字符串进行排序, ab。 由于在Java中是不可能的,因此我们首先将它们转换为 字符数组
  2. 对于较短字符串中出现的每个字符,我们逐字母检查:
    • 如果字符串中的字符 不等于字符串中的相应字符 b:
      • 返回此字符。
  3. 返回字符串的最后一个字符 因为这是额外的角色
  4. 打印结果

查找差异Leetcode解决方案的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    sort(a.begin() , a.end());
    sort(b.begin() , b.end());
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] != b[i])
            return b[i];
    return b[n];
}

int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

Java程序

import java.util.Arrays;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        char[] a_CharArray = a.toCharArray();
        char[] b_charArray = b.toCharArray();

        Arrays.sort(a_CharArray);
        Arrays.sort(b_charArray);

        int n = a.length();
        for(int i = 0 ; i < n ; i++)
            if(a_CharArray[i] != b_charArray[i])
                return b_charArray[i];
        return b_charArray[n];
    }
}
f

查找差异Leetcode解决方案的复杂性分析

时间复杂度

O(NlogN),其中N =较长字符串的长度。 我们对花费O(NlogN)时间的字符串/字符数组进行排序。

空间复杂度

上) 在Java和 O(1) 在C ++中,因为我们将字符串转换为 字符数组 在Java中。

方式(散列)

在这两个字符串中,我们都可以按其频率对每个字符进行哈希运算,并找到频率不同的字符。 由于我们有恒定数量的唯一字符。 该算法比上面讨论的算法更快。 作为有效的实施,我们可以创建一个 哈希表 并增加字符串中每个字符的频率 a 并降低字符串中每个字符的频率 b. 这将使我们只遇到一个字符的频率为 非零 这将是字符串中的多余字符 b.

算法

  1. 初始化哈希表以将所有字符的频率存储为 频率
  2. 对于字符串中的每个字符 a:
    • 在哈希表中增加其频率
  3. 对于字符串中的每个字符 b:
    • 降低其在哈希表中的频率
    • 如果其频率等于 -1:
      • 返回这个字符
  4. 返回“-”以保持函数语法
  5. 打印结果

查找差异Leetcode解决方案的实现

C ++程序

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    unordered_map <int , int> frequency;
    for(char &c : a)
        frequency[c]++;
    for(char &c : b)
    {
        frequency[c]--;
        if(frequency[c] == -1)
            return c;
    }
    //this case will never happen
    return '-';
}


int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

Java程序

import java.util.*;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        HashMap <Character , Integer> frequency = new HashMap<>();
        char x;
        for(int i = 0 ; i < a.length() ; i++)
        {
            x = a.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) + 1);
        }

        for(int i = 0 ; i < b.length() ; i++)
        {
            x = b.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) - 1);
            if(frequency.getOrDefault(x , 0) == -1)
                return x;
        }
        //this case will never occur
        return '-';
    }
}
f

查找差异Leetcode解决方案的复杂性分析

时间复杂度

上),N =较长字符串的大小,因为我们遍历两个字符串一次以更新其字符频率。

空间复杂度

O(1)。 尽管我们使用哈希表存储字符及其频率,但是无论输入内容如何,​​我们都使用恒定的空间。 因此,空间复杂度是恒定的。