បន្ថែមនិងស្វែងរកពាក្យ - រចនារចនាសម្ព័ន្ធទិន្នន័យ LeetCode


កម្រិតលំបាក មធ្យម
បទថយក្រោយ រចនាដោយ ខ្សែអក្សរ ទ្រី

បញ្ហា "បន្ថែមនិងស្វែងរកពាក្យ - រចនារចនាសម្ព័ន្ធរចនាទិន្នន័យ" LeetCode "ស្នើឱ្យយើងបង្កើតឬរចនាថ្មី រចនាសម្ព័ន្ធទិន្នន័យ។ បែបនោះដែលអាចត្រូវបានប្រើសម្រាប់បន្ថែមឬរក្សាទុកពាក្យហើយស្វែងរកពាក្យដែលមុខងារស្វែងរកអាចស្វែងរកសូម្បីតែកន្សោមធម្មតាពីពាក្យ។

ឧទាហរណ៍ៈ

ប្រសិនបើខ្សែអក្សរ / ពាក្យ =“ អេ” ត្រូវបានរក្សាទុកនៅក្នុងផែនទីនោះមុខងារដូចខាងក្រោមនឹងផ្តល់លទ្ធផលដូចគ្នា -

1. ស្វែងរក (..y) ។

ការស្វែងរក (។ ។ ) ។

3. ស្វែងរក (h .. ) ។

ទាំងបីខាងលើ មុខងារ ការហៅទូរស័ព្ទនឹងមានលទ្ធផលជាលទ្ធផល។

បន្ថែមនិងស្វែងរកពាក្យ - រចនារចនាសម្ព័ន្ធទិន្នន័យ 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. បន្ទាប់ពីនោះចាប់ផ្តើមប្តូរទំហំបាន អារេ នៃប្រភេទខ្សែអក្សរនិងមួយ ហាប់ម៉ាប់ នៃប្រភេទនៃគូនៃខ្សែអក្សរនិងប្រភេទចំនួនគត់។
  3. បង្កើតមុខងារដើម្បីបន្ថែមពាក្យនៅក្នុងរចនាសម្ព័ន្ធទិន្នន័យថ្មីដែលទទួលយកក ខ្សែអក្សរ អថេរជាប៉ារ៉ាម៉ែត្ររបស់វា។
  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

កូដចាវ៉ាសម្រាប់បន្ថែមនិងស្វែងរកពាក្យ - រចនារចនាសម្ព័ន្ធទិន្នន័យ 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 * ម) ដែល n គឺជាចំនួនពាក្យដែលបានបន្ថែមហើយ m គឺជាប្រវែងនៃពាក្យដែលត្រូវស្វែងរក។

ភាពស្មុគស្មាញនៃលំហ

អូរ (n) ពីព្រោះកម្មវិធីនេះប្រើចន្លោះសម្រាប់ធាតុ n នៅក្នុងអារេដែលអាចផ្លាស់ប្តូរបាននិងហេមដូច្នេះភាពស្មុគស្មាញនៃលំហគឺ O (n) ។

ឯកសារយោង