Word қосу және іздеу - LeetCode мәліметтер құрылымын жобалау


Күрделілік дәрежесі орта
Кері шегіну жобалау String Три

«Word қосу және іздеу - LeetCode мәліметтер құрылымын жобалау» мәселесі бізден жаңасын жасауды немесе жобалауды сұрайды мәліметтер құрылымы. Іздеу функциясы сөзден тұрақты тіркесті де іздей алатын сөзді қосу немесе сақтау және сөздерді іздеу үшін қолданыла алады.

Мысалы :

Егер картада string / word = “эй” сақталса, онда келесі функциялар бірдей нәтиже береді -

1. іздеу (..y).

2. іздеу (.e.).

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. Осыдан кейін, өлшемі өзгертілетін инициализация массив жол типі және а хэшмап жіптің типі және бүтін тип.
  3. А-ны қабылдайтын жаңа деректер құрылымына сөз қосу функциясын жасаңыз жол оның параметрі ретінде айнымалы.
  4. Осыдан кейін, берілген жолдың картада бар-жоғын тексеріп, оралыңыз.
  5. Берілген жолды массивтің соңғы индексіне және картаға салыңыз.
  6. Сол сияқты, жолдың айнымалысын параметр ретінде қабылдайтын жаңа деректер құрылымында сөзді іздеу үшін тағы бір функция жасаңыз.
  7. Берілген жол айнымалысын картадан іздеу.
  8. егер жол айнымалы “True” картасына басылған.
  9. Басқа тұрақты тіркесті тексеріңіз. Егер ол табылса, «True» басып шығарыңыз.
  10. «Жалған» басып шығарыңыз.

Іске асыру

Word қосуға және іздеуге арналған 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

Word қосу және іздеу үшін 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

Word қосу және іздеу үшін кешенділікті талдау - LeetCode мәліметтер құрылымын жобалау

Уақыттың күрделілігі

O (n * m) Мұндағы n - қосылған сөздер саны, m - ізделетін сөздердің ұзындығы.

Ғарыштың күрделілігі

O (N) өйткені бұл бағдарлама өлшемді массив пен хэшмаптағы n элементтерге арналған орынды пайдаланады, сондықтан кеңістіктің қиындығы O (n) құрайды.

Әдебиеттер тізімі