Минимальное количество шагов для создания двухстрочных решений Leetcode для анаграммы  


Сложный уровень Легко
Часто спрашивают в Амазонка Bloomberg Citrix Microsoft Twitter
алгоритмы кодирование Интервью подготовка к собеседованию LeetCode LeetCodeSolutions строка

Постановка задачи  

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

Пример

s = "bab", t = "aba"
1
s = "leetcode", t = "practice"
5

Минимальное количество шагов для создания анаграммы из двух строкшпилька

Подход  

Понятно, что одинаковые символы в обеих строках не требуют никаких операций (так как нам нужно их одновременное присутствие, а не одинаковый порядок). Важная часть - понять, как мы можем решить остальные символы.

Допустим, мы сначала очистили все символы в строке 's', которые соответствуют некоторому символу в строке 't', а затем удалили эти соответствующие символы в строке 't'. Пример s = «джинни», t = «гарри». После удаления совпадающих символов в обеих строках s = «ginn», t = «harr». Теперь очевидно, что каждый символ в строке 't' должен можно заменить на какой-либо другой символ, чтобы в нем также присутствовали символы 's'.

Помните, что мы уже удалили все пары соответствий в 's' и 't'. Таким образом, в «t» не будет символа, который присутствует в «s». Это легко реализовать с помощью хеш-таблицы.

Смотрите также
Решение Leetcode для расстояния Хэмминга

Реализация минимального количества шагов для создания двухстрочных решений анаграммы Leetcode

Программа C ++

#include <bits/stdc++.h>

using namespace std;

int minSteps(string s, string t) {
    unordered_map <int , int> f;
    int ans = 0;
    for(char &c : s) {
        f[c - 'a']++;
    }

    for(char &c : t) {
        f[c - 'a']--;
    }

    for(auto &c : f) {
        if(c.second != 0)
            ans++;
    }

    return ans / 2;
}

int main() {
    string s = "bab" , t = "aba";
    cout << minSteps(s , t) << endl;
    return 0;
}

Программа Java

import java.util.*;
import java.io.*;
import java.util.Hashtable;
import java.util.Set;
import java.util.Iterator;

class anagrams {
    public static void main(String args[]) {
        String s = "bab" , t = "aba";
        System.out.println(minSteps(s , t));
    }

    public static int minSteps(String s , String t) {

        Hashtable <Character , Integer> f = new Hashtable<>();
        int ans = 0;
        for(char c : s.toCharArray()) {
            f.put(c , f.getOrDefault(c , 0) + 1);
        }

        for(char c : t.toCharArray()) {
            f.put(c , f.getOrDefault(c , 0) - 1);
        }

        for(char c = 'a' ; c <= 'z' ; c++) {
            if(f.containsKey(c) && f.get(c) != 0) {
                ans += Math.abs(f.get(c));
            }
        }

        return ans / 2;
    }
}
1

Анализ сложности минимального количества шагов для создания двухстрочных решений анаграммы Leetcode

Сложность времени

O (N), где N = длина строки 's' и 't'.

Космическая сложность 

O (1), поскольку количество уникальных символов в обеих строках ограничено, мы знаем, что объем памяти остается постоянным.

1