Ελάχιστος αριθμός βημάτων για τη δημιουργία δύο συμβολοσειρών Anagram Leetcode Solutions  


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις αμαζόνα Bloomberg Citrix Microsoft Twitter
αλγόριθμοι κωδικοποίησης συνέντευξη συνέντευξηprep LeetCode LeetCodeSolutions κορδόνι

Δήλωση προβλήματος  

Σε αυτό το πρόβλημα, μας δίνονται δύο χορδές Το 's' & 't' αποτελείται από πεζούς αγγλικούς χαρακτήρες. Σε μία λειτουργία, μπορούμε να επιλέξουμε οποιονδήποτε χαρακτήρα στη συμβολοσειρά 't' και να τον αλλάξουμε σε κάποιον άλλο χαρακτήρα. Πρέπει να βρούμε τον ελάχιστο αριθμό τέτοιων εργασιών για να κάνουμε «t» ανάγραμμα του 's'.

Παράδειγμα

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

Ελάχιστος αριθμός βημάτων για τη δημιουργία δύο χορδών στο γράφημαΚαρφώστε

Προσέγγιση  

Είναι σαφές ότι οι χαρακτήρες που είναι ίδιοι και στις δύο χορδές δεν απαιτούν καμία λειτουργία (καθώς χρειαζόμαστε την ταυτόχρονη παρουσία τους, όχι την ίδια σειρά). Το σημαντικό μέρος είναι να καταλάβουμε πώς μπορούμε να λύσουμε για τους υπόλοιπους χαρακτήρες.

Ας υποθέσουμε ότι πρώτα διαγράψαμε όλους τους χαρακτήρες στη συμβολοσειρά που αντιστοιχούν σε κάποιο χαρακτήρα στη συμβολοσειρά 't' και μετά διαγράψαμε αυτούς τους αντίστοιχους χαρακτήρες στη συμβολοσειρά 't'. Παράδειγμα s = "ginny", t = "harry". Αφού αφαιρέσετε τους αντίστοιχους χαρακτήρες και στις δύο χορδές, s = "ginn", t = "harr". Τώρα, είναι προφανές ότι κάθε χαρακτήρας στη συμβολοσειρά «t» πρέπει να αλλάξετε σε κάποιον άλλο χαρακτήρα, έτσι ώστε οι χαρακτήρες του 's' να υπάρχουν επίσης σε αυτό.

Θυμηθείτε ότι είχαμε ήδη αφαιρέσει όλα τα ζευγάρια αντιστοιχιών στα 's' και 't'. Έτσι, δεν θα υπάρχει χαρακτήρας στο 't' που υπάρχει στο 's'. Αυτό μπορεί εύκολα να εφαρμοστεί με τη βοήθεια ενός πίνακα κατακερματισμού.

Βλέπε επίσης
Λύση Leetcode Hamming Distance

Εφαρμογή ελάχιστου αριθμού βημάτων για τη δημιουργία δύο συμβολοσειρών Anagram Leetcode Solutions

Πρόγραμμα 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), όπου Ν = μήκη συμβολοσειράς 's' & 't'.

Διαστημική πολυπλοκότητα 

O (1), καθώς υπάρχει περιορισμένος αριθμός μοναδικών χαρακτήρων και στις δύο χορδές, γνωρίζουμε ότι ο χώρος μνήμης παραμένει σταθερός.

1