Добавяне и търсене на дума - дизайн на структурата на данни LeetCode


Ниво на трудност M
връщане назад Дизайн Низ Трие

Проблемът „Добавяне и търсене на дума - дизайн на структурата на данните LeetCode“ ни изисква да създадем или проектираме нов структура на данни. Такава, която може да се използва за добавяне или съхраняване на дума и търсене на думите, където функцията за търсене може да търси дори регулярен израз от думата.

Например :

Ако низ / дума = „хей“ се съхранява в картата, следните функции ще дадат същия изход -

1. търсене (..y).

2. търсене (напр.).

3. търсене (ч ..).

Всички горепосочени три функция обажданията ще доведат до изхода да бъде истина.

Добавяне и търсене на 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. След това инициализирайте променлива масив от тип низ и a hashmap от типа на двойката низ и целочисления тип.
  3. Създайте функция за добавяне на думата в новата структура на данни, която приема a низ променлива като свой параметър.
  4. След това проверете дали дадения низ вече присъства в картата, върнете се.
  5. В противен случай вмъкнете дадения низ в последния индекс на масива и в картата също.
  6. По същия начин създайте друга функция за търсене на думата в новата структура на данни, която приема променлива на низ като свой параметър.
  7. Потърсете дадената променлива на низ на картата.
  8. Ако низ променливата присъства в печата на картата „True“.
  9. В противен случай проверете регулярния израз. Ако бъде намерен, отпечатайте “True”.
  10. Отпечатайте “False”.

изпълнение

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

Сложност във времето

O (n * m) където n е броят на добавените думи и m е дължината на думите, които трябва да се търсят.

Сложност на пространството

О (п) тъй като тази програма използва пространство за n елемента в променящия се масив и хеш-карта, следователно сложността на пространството е O (n).

Препратки