İki Simli Anagram Leetcode Həlləri TutorialCup Edilməsi üçün Minimum Adım Sayı

Mündəricat

Problem bəyanat

Bu problemdə bizə ikisi verilir strings 'Nin' & 't "aşağı halda English simvol ibarət. Bir əməliyyatda 't' sətrində hər hansı bir simvolu seçib başqa bir xarakterə dəyişə bilərik. 'T' an etmək üçün bu cür əməliyyatların minimum sayını tapmaq lazımdır anagram 'nin'.

misal

s = "bab", t = "aba"

s = "leetcode", t = "practice"

Yanaşma

Aydındır ki, hər iki simdə də eyni olan simvollar heç bir əməliyyat tələb etmir (çünki eyni sıraya yox, eyni zamanda varlığına ehtiyacımız var). Vacib hissə, qalan charcters üçün necə həll edə biləcəyimizi anlamaqdır.

Tutaq ki, əvvəlcə 's' sətrindəki 't' sətrindəki bəzi simvolla uyğun gələn bütün simvolları təmizlədik və sonra 't' sətrindəki uyğun simvolları sildik. Nümunə s = "cin", t = "harri". Hər iki simdə də uyğun simvollar götürüldükdən sonra s = “ginn”, t = “harr”. İndi 't' sətrindəki hər bir simvol açıqdır gərək 's' simvollarının da orada olması üçün başqa bir xarakterə dəyişdirin.

Unutmayın ki, 's' və 't' dəki bütün cüt cütlükləri artıq sildik. Beləliklə, 's' -də mövcud olan 't' -də heç bir xarakter olmayacaqdır. Bu asanlıqla bir hash masa köməyi ilə həyata keçirilə bilər.

İki Simli Anagram Leetcode Çözümlərinin Edilməsi üçün Minimum Adım sayının həyata keçirilməsi

C ++ Proqramı

#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 Proqramı

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

İki simli anagram leetcode həlləri etmək üçün minimum addım sayının mürəkkəbliyi təhlili

Zamanın mürəkkəbliyi

O (N), burada N = 's' və 't' sətirlərinin uzunluqları.

Kosmik Mürəkkəblik

O (1), hər iki sətirdə məhdud sayda bənzərsiz simvol olduğu üçün yaddaş məkanının sabit qaldığını bilirik.