Додавање и претраживање речи - дизајн структуре података ЛеетЦоде


Ниво тешкоће Средњи
Бацктрацкинг Дизајн низ Трие

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

На пример :

Ако је стринг / ворд = "хеј" сачуван на мапи, следеће функције ће дати исти излаз -

1. претрага (..и).

2. претрага (.н.).

3. претрага (ч ..).

Сва три горе наведена функција позиви ће резултирати истинитошћу резултата.

Додавање и претраживање речи - дизајн структуре података ЛеетЦоде

Пример

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. Након тога, иницијализујте величину која се може променити поредак типа стринга и а хасхмап типа пара низа и целобројног типа.
  3. Направите функцију за додавање речи у нову структуру података која прихвата а низ променљива као свој параметар.
  4. После тога проверите да ли је дати низ већ присутан на мапи, вратите се.
  5. Иначе унесите дати низ у последњи индекс низа и такође у мапу.
  6. Слично томе, креирајте другу функцију за претрагу речи у новој структури података која прихвата променљиву низа као свој параметар.
  7. Претражите задату променљиву низа на мапи.
  8. Ако низ променљива је присутна у испису мапе „Труе“.
  9. Иначе проверите регуларни израз. Ако је пронађено, испишите „Труе“.
  10. Одштампајте „Фалсе“.

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

Ц ++ код за додавање и претраживање речи - дизајн структуре података ЛеетЦоде

#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

Јава код за додавање и претраживање речи - дизајн структуре података ЛеетЦоде

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

Анализа сложености за додавање и претраживање речи - дизајн структуре података ЛеетЦоде

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

На М) где је н број додатих речи, а м дужина речи које треба претражити.

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

Он) јер овај програм користи простор за н елемената у променљивом низу и хеш-мапи, па је сложеност простора О (н).

Референце