단어 추가 및 검색 – 데이터 구조 설계 LeetCode  


난이도 중급
알고리즘 역 추적 코딩 디자인 인터뷰 인터뷰 준비 리트코드 LeetCodeSolutions 시도

“단어 추가 및 검색 – 데이터 구조 설계 LeetCode”문제는 새로운 데이터 구조. 단어를 추가하거나 저장하고 검색 기능이 단어에서 정규식도 검색 할 수있는 단어를 검색하는 데 사용할 수 있습니다.

예 :

문자열 / 단어 = "hey"가 맵에 저장되면 다음 함수는 동일한 출력을 제공합니다.

1. 검색 (..y).

2. 검색 (.e.).

3. 검색 (h ..).

위의 세 가지 모두 기능 호출하면 출력이 true가됩니다.

단어 추가 및 검색-데이터 구조 설계 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. "False"를 인쇄하십시오.
참조
팩토리얼 후행 제로 Leetcode 솔루션

실시  

단어 추가 및 검색을위한 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

단어 추가 및 검색을위한 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

단어 추가 및 검색에 대한 복잡성 분석 – 데이터 구조 설계 LeetCode  

시간 복잡성

O (n * m) 여기서 n은 추가 된 단어 수이고 m은 검색 할 단어의 길이입니다.

공간 복잡성

O (N) 이 프로그램은 크기 조정이 가능한 배열과 해시 맵의 n 요소에 공간을 사용하기 때문에 공간 복잡성은 O (n)입니다.

참조