Anagram Leetcode- ի լուծումներ երկու լար կատարելու համար քայլերի նվազագույն քանակը


Դժվարության մակարդակ Հեշտ
Հաճախակի հարցնում են Amazon Bloomberg Citrix Microsoft ծլվլոց
String

Խնդիրի հայտարարություն

Այս խնդրում մեզ երկու են տալիս տողերը 's' & 't' բաղկացած փոքրատառ անգլերեն նիշերից: Մի գործողության արդյունքում մենք կարող ենք ընտրել «t» տողի ցանկացած նիշ և այն փոխել ինչ-որ այլ նիշի: Մենք պետք է գտնենք նման գործողությունների նվազագույն քանակը `« տ »-ն անելու համար Անդրոգրաֆիա ի 'ի'

Օրինակ

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

Երկու լար պատրաստելու քայլերի նվազագույն քանակը Anagram

Մոտեցում

Հասկանալի է, որ երկու տողերում նույն նիշերը չեն պահանջում որևէ գործողություն (քանի որ մեզ պետք է դրանց միաժամանակյա ներկայությունը, ոչ թե նույն կարգը): Կարևոր մասը հասկանալն է, թե ինչպես կարող ենք լուծել մնացած պատառաքաղները:

Ասենք, որ մենք նախ մաքրեցինք տողի '' բոլոր նիշերը, որոնք համընկնում են 't' տողի որոշ նիշերի հետ, ապա ջնջեցինք 't' տողի այդ համապատասխան նիշերը: Օրինակ s = «ginny», t = «harry»: Երկու տողերում համընկնող նիշերը հեռացնելուց հետո s = «ginn», t = «harr»: Այժմ ակնհայտ է, որ «t» տողի յուրաքանչյուր նիշ պետք է վերափոխվել է ինչ-որ այլ նիշի, որպեսզի դրանում լինեն նաև «ն» -ի նիշերը:

Հիշեք, որ մենք արդեն հեռացրել էինք «և» -ի «և» տողերի բոլոր զույգերը: Այսպիսով, «t» - ի մեջ չի լինի այնպիսի նիշ, որն առկա է «s» - ներում: Դա հեշտությամբ կարելի է իրականացնել hash աղյուսակի միջոցով:

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 լուծումներ կատարելու համար երկու լար կատարելու համար քայլերի նվազագույն քանակի բարդության վերլուծություն

Timeամանակի բարդություն

O (N), որտեղ N = տողի '&' t 'երկարությունները:

Տիեզերական բարդություն 

O (1), քանի որ երկու տողերում էլ եզակի նիշերի սահմանափակ քանակ կա, մենք գիտենք, որ հիշողության տարածքը մնում է հաստատուն: