Word နှင့် Add Word Search - LeetCode ဒေတာဖွဲ့စည်းပုံပုံစံ


ခက်ခဲအဆင့် အလယ်အလတ်
နောက်ပြန် ပုံစံ ကြိုး Trie

ပြသနာ“ စကားလုံးပေါင်းထည့်ခြင်းနှင့်ရှာဖွေခြင်း - ဒေတာဖွဲ့စည်းပုံ LeetCode ဒီဇိုင်း” သည်ကျွန်ုပ်တို့အားအသစ်ဖန်တီးရန်သို့မဟုတ်ဒီဇိုင်းဆွဲရန်တောင်းဆိုသည် ဒေတာဖွဲ့စည်းပုံ။ စကားလုံးတစ်လုံးကိုပေါင်းထည့်ခြင်းသို့မဟုတ်သိုလှောင်ခြင်းနှင့်ရှာဖွေမှုလုပ်ဆောင်ချက်သည်စကားလုံးမှပုံမှန်အသုံးအနှုန်းကိုပင်ရှာဖွေနိုင်သောနေရာတွင်ရှာဖွေနိုင်သည်။

ဥပမာအားဖြင့် :

အကယ်၍ string / word =“ hey” ကိုမြေပုံထဲမှာသိမ်းထားရင်၊

1. ရှာဖွေရေး (..y) ။

2. ရှာဖွေရေး (.e ။ )

3. ရှာဖွေရေး (ဇ .. ) ။

အားလုံးသုံးအထက်ပါ function ကို ခေါ်ဆိုမှုများစစ်မှန်တဲ့ဖြစ် output ကိုဖြစ်ပေါ်လိမ့်မည်။

Word နှင့် Add Word Search - 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

Resizable ခင်းကျင်းခြင်းနှင့် Hashmap ကိုအသုံးပြုခြင်း

algorithm

  1. ဒေတာအသစ်ဖွဲ့စည်းပုံအတွက်အတန်းတစ်ခုကိုအစပြုပါ။
  2. ထို့နောက် resizable ကိုစတင်ပါ အခင်းအကျင်း string ကိုအမျိုးအစားနှင့်တစ် ဦး ၏ hashmap string ကို၏ pair တစုံအမျိုးအစားနှင့်ကိန်းအမျိုးအစား။
  3. a ကိုလက်ခံသည့်ဒေတာဖွဲ့စည်းပုံအသစ်တွင်စကားလုံးကိုထည့်ရန် function တစ်ခုကိုဖန်တီးပါ ကြိုး ယင်း၏ parameter သည်အဖြစ် variable ကို။
  4. ပြီးနောက်၊ ပေးထားသော string သည်မြေပုံတွင်ရှိနှင့်ပြီး၊ ပြန်လာပါစစ်ဆေးပါ။
  5. အခြားအရာသည်ပေးထားသော string ကို array ၏နောက်ဆုံးအညွှန်းနှင့်မြေပုံတွင်လည်းထည့်ပါ။
  6. ထိုနည်းတူစွာပင် string variable ကို၎င်း၏ parameter သည်အဖြစ်လက်ခံသောဒေတာအသစ်ဖွဲ့စည်းပုံမှာစကားလုံးရှာဖွေအခြား function ကိုဖန်တီးပါ။
  7. ပေးထားသော string variable ကိုမြေပုံပေါ်တွင်ရှာပါ။
  8. အလိုလျှင် ကြိုး variable မြေပုံပုံနှိပ် "True" တွင်ပစ္စုပ္ပန်ဖြစ်ပါတယ်။
  9. ကျန်ပုံမှန်အသုံးအနှုန်းကိုစစ်ဆေးပါ။ အကယ်၍ ၎င်းကိုရှာပါက“ True” ကိုရိုက်ပါ။
  10. “ False” ကိုပုံနှိပ်ပါ။

အကောင်အထည်ဖော်ရေး

Add and Search Word အတွက် C ++ code - 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

Add and Search 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

Add and Search Word အတွက်ရှုပ်ထွေးမှုအားခွဲခြမ်းစိတ်ဖြာခြင်း - LeetCode ဒေတာဖွဲ့စည်းပုံပုံစံ

အချိန်ရှုပ်ထွေး

အို (n * m) n သည်ထည့်သွင်းထားသောစာလုံးအရေအတွက်နှင့် m သည်ရှာဖွေရမည့်စကားလုံးများ၏အရှည်ဖြစ်သည်။

အာကာသရှုပ်ထွေးမှု

အို (ဎ) ဘာလို့လဲဆိုတော့ဒီပရိုဂရမ်က resizable array နဲ့ hashmap မှာ n element တွေအတွက် space ကိုသုံးထားလို့ပါ။

ကိုးကား