Минимален брой стъпки за направа на два струни Anagram Leetcode Solutions  


Ниво на трудност Лесно
Често задавани в Амазонка Bloomberg Citrix Microsoft кикотене
алгоритми кодиране Интервю интерпретация LeetCode LeetCodeSolutions Низ

Декларация за проблема  

В този проблем ни дават две струни 's' & 't', състоящ се от малки букви на английски език. В една операция можем да изберем всеки символ в низ „t“ и да го променим на друг символ. Трябва да намерим минималния брой такива операции, за да направим 't' an анаграма на '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'. Това може лесно да бъде приложено с помощта на хеш таблица.

Вижте също
Разтвор на Hameting Leetcode

Прилагане на минимален брой стъпки за направа на два струни Anagram 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

Анализ на сложността на минималния брой стъпки за направа на два струни Anagram Leetcode Solutions

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

O (N), където N = дължини на низ 's' & 't'.

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

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