Найдите отличия от решения Leetcode


Сложный уровень Легко
Часто спрашивают в саман Амазонка Google
хеширования строка

В этой задаче нам даны два струны. Вторая строка генерируется путем случайного перемешивания символов первой строки с последующим добавлением дополнительного символа в любую случайную позицию. Нам нужно вернуть лишний символ, который был добавлен во вторую строку. Символы всегда будут строчными английскими буквами.

Пример

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

Объяснение # 1

Дополнительный символ, добавляемый к строке b 'f' как строка a не содержит.

Объяснение # 2

строка имеет 4 буквы 'a', а строка имеет 5. Итак, дополнительная буква - «а».

Подход (сортировка)

Мы можем отсортировать обе строки, а затем перебрать их по буквам, чтобы найти первую позицию, в которой они различаются. Во второй строке всегда будет один дополнительно персонаж. Итак, мы всегда найдем точку, где строка a и b отличается. Однако может быть случай, когда строка b после сортировки соответствует каждому символу в строке a in, но в конце имеет один лишний символ. Нам нужно разобраться с этим одним частным случаем.

Найдите отличия от решения Leetcode

Алгоритм

  1. Отсортируйте обе строки, a и b. Поскольку это невозможно в 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 ++, поскольку мы конвертируем строки в char Массивы в 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). Хотя мы используем хеш-таблицу для хранения символов с указанием их частот, мы используем постоянное пространство независимо от ввода. Итак, сложность пространства постоянна.