Προσθήκη και αναζήτηση Word - Σχεδιασμός δομής δεδομένων LeetCode


Επίπεδο δυσκολίας Μέσον
Οπισθοδρόμηση Σχέδια κορδόνι Τρι

Το πρόβλημα «Προσθήκη και Αναζήτηση Word - Σχεδιασμός δομής δεδομένων LeetCode» μας ζητά να δημιουργήσουμε ή να σχεδιάσουμε ένα νέο δομή δεδομένων. Αυτό που μπορεί να χρησιμοποιηθεί για την προσθήκη ή αποθήκευση μιας λέξης και την αναζήτηση των λέξεων όπου η λειτουργία αναζήτησης μπορεί να αναζητήσει ακόμη και μια κανονική έκφραση από τη λέξη.

Για παράδειγμα :

Εάν η συμβολοσειρά / λέξη = "hey" είναι αποθηκευμένη στο χάρτη, οι ακόλουθες συναρτήσεις θα δώσουν την ίδια έξοδο -

1. αναζήτηση (..y).

2. αναζήτηση (.e.).

3. αναζήτηση (h ..).

Όλα τα παραπάνω τρία λειτουργία Οι κλήσεις θα έχουν ως αποτέλεσμα την έξοδο να είναι αληθής.

Προσθήκη και αναζήτηση Word - Σχεδιασμός δομής δεδομένων LeetCode

Παράδειγμα

addword ("code")
addword ("java")
addword ("when")
search ("blue")
search ("java")
search ("co..")
False
True
True
addword ("who")
addword ("why")
search ("why")
search ("hey")
search ("the")
True
False
False

Χρησιμοποιώντας πίνακα με δυνατότητα αλλαγής μεγέθους και Hashmap

Αλγόριθμος

  1. Αρχικοποιήστε μια κλάση για τη νέα δομή δεδομένων.
  2. Μετά από αυτό, αρχικοποιήστε μια αλλαγή μεγέθους παράταξη τύπου συμβολοσειράς και α κατακερματισμός του τύπου του ζεύγους της συμβολοσειράς και του ακέραιου τύπου.
  3. Δημιουργήστε μια συνάρτηση για να προσθέσετε τη λέξη στη νέα δομή δεδομένων που δέχεται ένα κορδόνι μεταβλητή ως παράμετρος της.
  4. Μετά από αυτό, ελέγξτε αν η δεδομένη συμβολοσειρά υπάρχει ήδη στο χάρτη, επιστρέψτε.
  5. Διαφορετικά, εισαγάγετε τη δεδομένη συμβολοσειρά στον τελευταίο κατάλογο του πίνακα και επίσης στον χάρτη.
  6. Ομοίως, δημιουργήστε μια άλλη συνάρτηση για να αναζητήσετε τη λέξη στη νέα δομή δεδομένων που δέχεται μια μεταβλητή συμβολοσειράς ως παράμετρος της.
  7. Αναζήτηση στη δεδομένη μεταβλητή συμβολοσειράς στο χάρτη.
  8. Εάν η κορδόνι υπάρχει μεταβλητή στην εκτύπωση χάρτη "True".
  9. Αλλιώς ελέγξτε την κανονική έκφραση. Εάν βρεθεί εκτυπώστε "True".
  10. Εκτύπωση "False".

Εκτέλεση

Κωδικός C ++ για Προσθήκη και Αναζήτηση Word - Σχεδιασμός δομής δεδομένων LeetCode

#include<bits/stdc++.h> 
using namespace std; 
  
class newStructure{ 
    vector <string> arr; 
      
    map <string, int> Map; 
  
    public: 
        void addword(string x){ 
            
            if(Map.find(x) != Map.end()) 
                return; 
                  
            int index = arr.size(); 
            arr.push_back(x); 
                  
            Map.insert(std::pair<string,int>(x, index)); 
        } 
              
              
        void search(string x){ 
            if(Map.find(x) != Map.end()){ 
                cout<<"True"<<endl;
                return;
            }    
            else{
                regex b(x);
                for(int i=0; i<arr.size(); i++){
                    if(regex_match(arr[i],b)){
                        cout<<"True"<<endl;
                        return;
                    }
                }
            }    
            cout<<"False"<<endl;
        } 
}; 
  
int main(){ 
    newStructure ds;
    
    ds.addword("code"); 
    ds.addword("java"); 
    ds.addword("when"); 
    
    ds.search("blue");
    ds.search("java");
    ds.search("co..");
    
    return 0;
}
False
True
True

Κωδικός Java για Προσθήκη και Αναζήτηση Word - Σχεδιασμός δομής δεδομένων LeetCode

import java.util.*; 
import java.util.regex.Pattern;

class newStructure{ 
    ArrayList<String> arr; 
    HashMap<String, Integer>  map; 
    
    public newStructure(){ 
        arr = new ArrayList<String>(); 
        map = new HashMap<String, Integer>(); 
    } 
    
    void addword(String x){ 
        if(map.get(x) != null) 
            return; 
        
        int s = arr.size(); 
        arr.add(x); 
        map.put(x, s); 
    } 
    
    void search(String x){ 
        if(map.get(x)!=null){
            System.out.println("True");
            return;
        } 
        else{
            Pattern regex = Pattern.compile(x);
            
            for(String s:arr){
                if(regex.matcher(s).matches()){
                    System.out.println("True");
                    return;
                }
            }
        }
        System.out.println("False");
    } 
} 

class Main{ 
    public static void main (String[] args){ 
        newStructure ds = new newStructure();
        
        ds.addword("code"); 
        ds.addword("java"); 
        ds.addword("when"); 
        
        ds.search("blue"); 
        ds.search("java"); 
        ds.search("co.."); 
        
    } 
}
False
True
True

Ανάλυση πολυπλοκότητας για Προσθήκη και Αναζήτηση Word - Σχεδιασμός δομής δεδομένων LeetCode

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

O (n * m) όπου n είναι ο αριθμός των λέξεων που προστίθενται και m είναι το μήκος των λέξεων προς αναζήτηση.

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

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

αναφορές