Даданне і пошук слова - дызайн структуры дадзеных LeetCode


Узровень складанасці серада
Фанаграмы дызайн Радок Тры

Праблема «Дадаць і шукаць слова - дызайн структуры дадзеных LeetCode» просіць нас стварыць альбо распрацаваць новы Структура дадзеных. Такая, якая можа быць выкарыстана для дадання альбо захоўвання слова і пошуку слоў, дзе функцыя пошуку можа шукаць нават рэгулярны выраз са слова.

Напрыклад :

Калі радок / слова = "эй" захоўваецца на карце, наступныя функцыі дадуць аднолькавы вынік -

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

Выкарыстанне зменнага масіва і хэш-карты

Алгарытм

  1. Ініцыялізаваць клас для новай структуры дадзеных.
  2. Пасля гэтага ініцыялізуйце зменны памер масіў тыпу радка і a хэшмап тыпу пары радка і цэлага тыпу.
  3. Стварыце функцыю, каб дадаць слова ў новую структуру дадзеных, якая прымае a радок зменная як яго параметр.
  4. Пасля гэтага праверце, ці ёсць дадзены радок ужо на карце, вярніцеся.
  5. У іншым выпадку ўстаўце дадзены радок у апошні індэкс масіва і на карту таксама.
  6. Аналагічным чынам стварыце яшчэ адну функцыю для пошуку слова ў новай структуры дадзеных, якая прымае ў якасці параметра параменную зменную.
  7. Шукайце на карце дадзеную радкавую зменную.
  8. Калі радок Зменная прысутнічае ў друку карты "Праўда".
  9. У адваротным выпадку праверыць рэгулярны выраз. Калі ён знойдзены, надрукуйце "True".
  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

Складанасць часу

O (п * м) дзе n - колькасць дададзеных слоў, m - даўжыня слоў, якія трэба шукаць.

Касмічная складанасць

Аб (п) паколькі гэтая праграма выкарыстоўвае прастору для n элементаў у змяняемым масіве і хэш-карце, таму складанасць прасторы складае O (n).

Спасылкі