Додај и Пребарај збор - Дизајн на структурата на податоците LeetCode


Ниво на тешкотија Медиум
Враќање назад дизајн Стринг Трие

Проблемот „Додај и Пребарај збор - Дизајн на структурата на податоците LeetCode“ нè замолува да креираме или дизајнираме нова структура на податоци. Такво што може да се користи за додавање или зачувување на збор и пребарување на зборови каде што функцијата за пребарување може да пребарува дури и редовен израз од зборот.

На пример:

Ако string / word = „еј“ е зачувана на картата, следниве функции ќе го дадат истиот излез -

1. пребарување (..y).

2. пребарување (.е.).

3. пребарување (ж ..).

Сите горенаведени три функција повиците ќе резултираат во излезот да биде точен.

Додај и Пребарај збор - Дизајн на структурата на податоците 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. Создадете функција за додавање на зборот во новата структура на податоци што прифаќа a низа променлива како нејзин параметар.
  4. После тоа, проверете дали дадената низа е веќе присутна на картата, вратете се.
  5. Друго вметнете ја дадената низа на последниот индекс на низата и во картата исто така.
  6. Слично на тоа, создадете друга функција за пребарување на зборот во новата структура на податоци што прифаќа низа променлива како нејзин параметар.
  7. Пребарувајте ја дадената низа променлива на картата.
  8. Ако низа променливата е присутна во отпечатокот на картата „Вистина“.
  9. Друго проверете го редовниот израз. Ако се најде, отпечатете „Точно“.
  10. Печати „Лажно“.

Имплементација

C ++ код за Додади и Пребарај збор - Дизајн на структурата на податоците 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 код за Додај и Пребарај збор - Дизајн на структурата на податоците 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

Анализа на сложеност за додавање и пребарување збор - Дизајн на структурата на податоците LeetCode

Временска комплексност

О (н * м) каде n е бројот на додадени зборови и m е должината на зборовите што треба да се пребаруваат.

Комплексноста на просторот

Тој) бидејќи оваа програма користи простор за n елементи во низата што може да се преобрази и во хашмапот, затоа, комплексноста на просторот е O (n).

Референци