Минимални број корака за прављење две струне Анаграм Леетцоде решења


Ниво тешкоће Лако
Често питани у амазонка Блоомберг Цитрик мицрософт твиттер
низ

Изјава о проблему

У овом проблему су нам дата два струне 'с' & 'т' састоји се од малих малих слова на енглеском. У једној операцији можемо одабрати било који знак у низу 'т' и променити га у неки други знак. Морамо пронаћи минималан број таквих операција да бисмо направили 'т' ан анаграм од 'с'.

Пример

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

Минималан број корака за прављење две жице Анаграм

Приступ

Јасно је да ликови који су исти у обе жице не захтевају никакве операције (јер нам је потребно њихово истовремено присуство, а не исти редослед). Важно је разумети како можемо решити остатак повеља.

Рецимо да смо прво обрисали све знакове у низу 'с' који се подударају са неким знаковима у низу 'т', а затим избрисали те одговарајуће знакове из низа 'т'. Пример с = "гинни", т = "Харри". Након уклањања одговарајућих знакова у оба низа, с = “гинн”, т = “харр”. Очигледно је да сваки знак у низу 'т' обавезан бити промењен у неки други знак тако да у њему буду присутни и ликови 'с'.

Запамтите да смо већ уклонили све парове подударања у 'с' и 'т'. Дакле, у 'т' неће бити знака који је присутан у 'с'. Ово се лако може применити уз помоћ хеш табеле.

Имплементација минималног броја корака за прављење две струне Анаграм Леетцоде решења

Програм Ц ++

#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;
}

Јава Програм

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

Анализа сложености минималног броја корака за прављење две струне Анаграм Леетцоде решења

Сложеност времена

О (Н), где је Н. = дужине низа 'с' & 'т'.

Сложеност простора 

О (1), пошто је у обе жице ограничен број јединствених знакова, знамо да меморијски простор остаје константан.