Βρείτε τη Διαφορά Leetcode Solution


Επίπεδο δυσκολίας Εύκολος
Συχνές ερωτήσεις πλίθα αμαζόνα Google
Hashing κορδόνι

Σε αυτό το πρόβλημα, μας δίνονται δύο χορδές. Η δεύτερη συμβολοσειρά δημιουργείται ανακατεύοντας τυχαία τους χαρακτήρες της πρώτης συμβολοσειράς και στη συνέχεια προσθέτοντας έναν επιπλέον χαρακτήρα σε οποιαδήποτε τυχαία θέση. Πρέπει να επιστρέψουμε τον επιπλέον χαρακτήρα που προστέθηκε στη δεύτερη συμβολοσειρά. Οι χαρακτήρες θα είναι πάντα πεζά γράμματα στα αγγλικά.

Παράδειγμα

a = "abcde" , b = "ebacdf"
f
a = "aaaa" , b = "aaaaa"
a

Επεξήγηση # 1

Ο επιπλέον χαρακτήρας που προστίθεται στη συμβολοσειρά b είναι «f» ως συμβολοσειρά a δεν το περιέχει.

Επεξήγηση # 2

κορδόνι έχει 4 γράμματα «a» ενώ είναι συμβολοσειρά έχει 5. Έτσι, το επιπλέον γράμμα είναι «a».

Προσέγγιση (Ταξινόμηση)

Μπορούμε να ταξινομήσουμε και τις δύο χορδές και στη συνέχεια να επαναλάβουμε και τις δύο επιστολές για να βρούμε την πρώτη θέση όπου διαφέρουν. Η δεύτερη συμβολοσειρά θα έχει πάντα μία επιπλέον χαρακτήρας. Έτσι, θα βρούμε πάντα ένα σημείο όπου το string a b διαφέρει. Ωστόσο, μπορεί να υπάρχει περίπτωση όπου η συμβολοσειρά b μετά την ταξινόμηση ταιριάζει με κάθε χαρακτήρα στη σειρά a στο αλλά έχει έναν επιπλέον χαρακτήρα στο τέλος. Πρέπει να χειριστούμε αυτήν την ειδική περίπτωση.

Βρείτε τη Διαφορά Leetcode Solution

Αλγόριθμος

  1. Ταξινόμηση και των δύο χορδών, a b. Δεδομένου ότι δεν είναι δυνατό στην Java, τα μετατρέπουμε πρώτα σε συστοιχίες char
  2. Για κάθε χαρακτήρα που υπάρχει στη συντομότερη συμβολοσειρά, κάνουμε έναν έλεγχο κατά γράμμα:
    • Εάν ο χαρακτήρας στο string δεν είναι ίσος με τον αντίστοιχο χαρακτήρα στη συμβολοσειρά b:
      • επιστρέψτε αυτόν τον χαρακτήρα.
  3. Επιστρέψτε τον τελευταίο χαρακτήρα της συμβολοσειράς καθώς είναι ο επιπλέον χαρακτήρας
  4. Εκτυπώστε το αποτέλεσμα

Εφαρμογή του Find the Difference Leetcode Solution

Πρόγραμμα C ++

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    sort(a.begin() , a.end());
    sort(b.begin() , b.end());
    int n = a.size();
    for(int i = 0 ; i < n ; i++)
        if(a[i] != b[i])
            return b[i];
    return b[n];
}

int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

Πρόγραμμα Java

import java.util.Arrays;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        char[] a_CharArray = a.toCharArray();
        char[] b_charArray = b.toCharArray();

        Arrays.sort(a_CharArray);
        Arrays.sort(b_charArray);

        int n = a.length();
        for(int i = 0 ; i < n ; i++)
            if(a_CharArray[i] != b_charArray[i])
                return b_charArray[i];
        return b_charArray[n];
    }
}
f

Ανάλυση πολυπλοκότητας του Find the Difference Leetcode Solution

Χρόνος πολυπλοκότητας

O (NlogN), όπου N = Μήκος της μεγαλύτερης συμβολοσειράς. Ταξινομούμε τις συμβολοσειρές / πίνακες char που χρειάζονται χρόνο O (NlogN).

Διαστημικότητα

ΕΠΙ) στην Ιάβα και Ο (1) στο C ++ καθώς μετατρέπουμε τις χορδές σε συστοιχίες char στην Ιάβα.

Προσέγγιση (κατακερματισμός)

Και στις δύο χορδές, μπορούμε να κατακερματίσουμε κάθε χαρακτήρα με τη συχνότητά του και να βρούμε τον χαρακτήρα που διαφέρει στη συχνότητα. Δεδομένου ότι έχουμε έναν σταθερό αριθμό μοναδικών χαρακτήρων. Αυτός ο αλγόριθμος είναι ταχύτερος από αυτόν που συζητήθηκε παραπάνω. Ως αποτελεσματική εφαρμογή, μπορούμε να δημιουργήσουμε ένα πίνακας κατακερματισμού και αυξήστε τη συχνότητα για κάθε χαρακτήρα στη συμβολοσειρά a και μείωση της συχνότητας για κάθε χαρακτήρα στη συμβολοσειρά b. Αυτό θα μας αφήσει σε μια περίπτωση όπου η συχνότητα ακριβώς ενός χαρακτήρα είναι μη μηδέν και αυτός θα είναι ο επιπλέον χαρακτήρας στη συμβολοσειρά b.

Αλγόριθμος

  1. Αρχικοποιήστε έναν πίνακα κατακερματισμού για να αποθηκεύσετε τη συχνότητα όλων των χαρακτήρων ως συχνότητα
  2. Για κάθε χαρακτήρα στη σειρά a:
    • αύξηση της συχνότητάς του στον πίνακα κατακερματισμού
  3. Για κάθε χαρακτήρα στη σειρά b:
    • μείωση της συχνότητάς του στον πίνακα κατακερματισμού
    • Εάν η συχνότητά του είναι ίση με -1:
      • επιστρέψτε αυτόν τον χαρακτήρα
  4. Return '-' για να διατηρηθεί η σύνταξη της λειτουργίας
  5. Εκτυπώστε το αποτέλεσμα

Εφαρμογή του Find the Difference Leetcode Solution

Πρόγραμμα C ++

#include <bits/stdc++.h>
using namespace std;

char findTheDifference(string a , string b)
{
    unordered_map <int , int> frequency;
    for(char &c : a)
        frequency[c]++;
    for(char &c : b)
    {
        frequency[c]--;
        if(frequency[c] == -1)
            return c;
    }
    //this case will never happen
    return '-';
}


int main()
{
    string a = "abcde" , b = "ebacdf";
    cout << findTheDifference(a , b) << '\n';

    return 0;
}

Πρόγραμμα Java

import java.util.*;

class find_the_difference
{
    public static void main(String args[])
    {
        String a = "abcde" , b = "ebacdf";
        System.out.println(findTheDifference(a , b));
    }

    static char findTheDifference(String a , String b)
    {
        HashMap <Character , Integer> frequency = new HashMap<>();
        char x;
        for(int i = 0 ; i < a.length() ; i++)
        {
            x = a.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) + 1);
        }

        for(int i = 0 ; i < b.length() ; i++)
        {
            x = b.charAt(i);
            frequency.put(x , frequency.getOrDefault(x , 0) - 1);
            if(frequency.getOrDefault(x , 0) == -1)
                return x;
        }
        //this case will never occur
        return '-';
    }
}
f

Ανάλυση πολυπλοκότητας του Find the Difference Leetcode Solution

Χρόνος πολυπλοκότητας

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

Διαστημικότητα

Ο (1). Αν και χρησιμοποιούμε ένα hashtable για την αποθήκευση χαρακτήρων με τις συχνότητές τους, χρησιμοποιούμε σταθερό χώρο ανεξάρτητα από την είσοδο. Έτσι, η διαστημική πολυπλοκότητα είναι σταθερή.