문자 트 라이 트 리 의 스 트림

제목

데이터 구조 문 제 는 사전 을 지정 하고 데이터 구 조 를 초기 화 합 니 다.매번 조회 할 때마다 한 글자 씩 주 고 되 돌아 오 는 정 보 는 bool 형식 입 니 다.현재 문자 부터 앞 을 보 는 K 개의 구 축 된 문자열 이 사전 에 떨 어 지면 K 되 돌려 줍 니 다 true 그렇지 않 으 면 false

데이터 범위: 1 <= words.length <= 2000, 1 <= words[i].length <= 2000, 조회 총수 가 초과 되 지 않 음 40000

사고의 방향

사전 의 문자열 을 반전 시 켜 사전 트 리 구축

조회 에서 쌍 단 대기 열 을 유지 하고 저장 전 T 문자, T = max words[i].length

한 글자 씩 오 면 사전 트 리 에서 검색 하면 됩 니 다

class StreamChecker {
public:
    vector<unordered_map<char, int>> tree;
    vector<bool> isleaf;
    int max_len;
    deque<int> q;
    void add_word(const string& s){
        int now = 0;
        for (int i = s.length() - 1; i >= 0; i--){
            auto ch = s[i];
            if (tree[now].find(ch) == tree[now].end()){
                tree[now][ch] = tree.size();
                now = tree.size();
                tree.push_back(unordered_map<char, int>());
                isleaf.push_back(false);
            }
            else{
                now = tree[now][ch];
            }
        }
        isleaf[now] = true;
    }
    StreamChecker(vector<string>& words) {
        tree.push_back(unordered_map<char, int>());
        isleaf.push_back(false);
        max_len = 0;
        for (auto& s : words){
            max_len = max(max_len, int(s.length()));
            add_word(s);
        }
    }
    bool query(char letter) {
        q.push_front(letter);
        if (q.size() > max_len)
            q.pop_back();
        int now = 0;
        for (auto it : q){
            if (tree[now].find(it) == tree[now].end())
                return false;
            now = tree[now][it];
            if (isleaf[now]){
                return true;
            }
       }
        return false;
    }

};
/**
 * Your StreamChecker object will be instantiated and called as such:
 * StreamChecker* obj = new StreamChecker(words);
 * bool param_1 = obj->query(letter);
 */

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

문자 트 라이 트 리 의 스 트림

제목 데이터 구조 문 제 는 사전 을 지정 하고 데이터 구 조 를 초기 화 합 니 다.매번 조회 할 때마다 한 글자 씩 주 고 되 돌아 오 는 정 보 는 bool 형식 입 니 다.현재 문자 부터 앞 을 보 는 K 개...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

문자 트 라이 트 리 의 스 트림

좋은 웹페이지 즐겨찾기