ቃል ያክሉ እና ይፈልጉ - የውሂብ መዋቅር ንድፍ LeetCode


የችግር ደረጃ መካከለኛ
ወደ ኋላ መመለስ ዕቅድ ሕብረቁምፊ ደርድር

ችግሩ “ቃልን ይጨምሩ እና ይፈልጉ - የውሂብ መዋቅር ንድፍ LeetCode” አዲስ እንድንፈጥር ወይም ዲዛይን እንድናደርግ ይጠይቃል የመረጃ አወቃቀር. እንዲህ ዓይነቱን ቃል ለመጨመር ወይም ለማከማቸት እና የፍለጋው ተግባር ከቃሉ ውስጥ መደበኛ አገላለፅን እንኳን ሊፈልግ በሚችልባቸው ቃላቶችን ለመፈለግ ሊያገለግል ይችላል።

ለአብነት :

ሕብረቁምፊ / ቃል = “ሄይ” በካርታው ውስጥ ከተከማቸ የሚከተሉት ተግባራት ተመሳሳይ ውጤት ያስገኛሉ -

1. ፍለጋ (..ይ)

2. ፍለጋ (.e.).

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

Resizable ድርድር እና ሃሽማፕን በመጠቀም

አልጎሪዝም

  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

የጊዜ ውስብስብነት

ኦ (n * m) የት n የቃላት ብዛት ታክሏል እና ሜትር የሚፈለጉት የርዝመቶች ርዝመት ነው ፡፡

የቦታ ውስብስብነት

ሆይ (n) ምክንያቱም ይህ ፕሮግራም ሊለዋወጥ በሚችል ድርድር እና ሀሽፕ ውስጥ ለ n ንጥረ ነገሮች ቦታን ይጠቀማል ፣ ስለሆነም የቦታ ውስብስብነት O (n) ነው።

ማጣቀሻዎች