가사 검색

1. 정렬 후 이분탐색

ex) [probb ,proaa, prozz,procc]는 정렬 후 [proaa,probb,procc,prozz]가 된다.

probb,procc는 proaa와 prozz 사이에 있음에 착안해서, ?를 a와 z로 바꾼후 그 사이에 있는 단어의 개수를 센다.

from collections import defaultdict
import bisect

def find_result(word,left,right):
    left_idx = bisect.bisect_left(word,left)
    right_idx = bisect.bisect_right(word,right)
    return right_idx-left_idx

def solution(words, queries):
    answer = []
    word_list = defaultdict(list)
    reversed_word_list = defaultdict(list)
    for word in words:
        word_list[len(word)].append(word)
        reversed_word_list[len(word)].append(word[::-1])

    for key in word_list.keys():
        word_list[key].sort()
        reversed_word_list[key].sort()

    for query in queries:
        if query[0] != '?':
            answer.append(find_result(word_list[len(query)],query.replace('?','a'),query.replace('?','z')))
        else:
            query = query[::-1]
            answer.append(find_result(reversed_word_list[len(query)],query.replace('?','a'),query.replace('?','z')))
    return answer

 

2. trie 자료구조

trie와 거꾸로된 trie를 만든다. pro?? 형태라면 trie를 탐색하고, 만약 ??pro 라면 거꾸로된 트라이를 탐색한다.

????? 형태라면 길이에 맞는 단어의 개수를 출력한다.

import sys
sys.setrecursionlimit(10**6)

def make_trie(trie, words):
    for word in words:
        cur = trie
        l = len(word)
        for w in word:
            if w in cur:
                cur = cur[w]
                cur['!'].append(l)
            else:
                cur[w] = {}
                cur = cur[w]
                cur['!'] = [l]
    return trie


def find_result(trie, query, length):
    cnt = 0
    if query[0] == '?':
        return trie['!'].count(length)
    elif query[0] in trie:
        cnt += find_result(trie[query[0]], query[1:], length)
    return cnt


def solution(words, queries):
    answer = []
    rev_words = []
    count_len_words = []
    for word in words:
        rev_words.append(word[::-1])
        count_len_words.append(len(word))

    trie = make_trie({}, words)
    rev_trie = make_trie({}, rev_words)

    for query in queries:
        if query[0] == '?' and query[-1] == '?':
            answer.append(count_len_words.count(len(query)))
        elif query[-1] == '?':
            answer.append(find_result(trie, query, len(query)))
        elif query[0] == '?':
            answer.append(find_result(rev_trie, query[::-1], len(query)))

    return answer