# trie 자료구조 사용
# https://blog.ilkyu.kr/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%97%90%EC%84%9C-Trie-%ED%8A%B8%EB%9D%BC%EC%9D%B4-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0
class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}


class Trie(object):
    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        curr_node = self.head

        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)

            curr_node = curr_node.children[char]

        curr_node.data = string

    def search(self, string):
        curr_node = self.head

        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return False

        if curr_node.data is not None:
            return True

    def starts_with(self, query):
        curr_node = self.head
        result = []
        subtrie = None

        prefix = ""
        for char in query:
            if char != '?':
                prefix += char

        # 트라이에서 prefix 를 찾고,
        # prefix의 마지막 글자 노드를 subtrie로 설정
        for char in prefix:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
                subtrie = curr_node
            else:
                return result

        # bfs 로 prefix subtrie를 순회하며
        # data가 있는 노드들(=완전한 단어)를 찾는다.
        queue = list(subtrie.children.values())

        while queue:
            curr = queue.pop()
            if curr.data is not None and len(curr.data) == len(query):
                result.append(curr.data)

            queue += list(curr.children.values())

        return result


# 효율성 테스트
# 테스트 1 〉	실패 (시간 초과)
# 테스트 2 〉	실패 (시간 초과)
# 테스트 3 〉	실패 (런타임 에러)
# 테스트 4 〉	실패 (시간 초과)
# 테스트 5 〉	통과 (5497.76ms, 787MB)
def solution(words, queries):
    answer = []

    trie = Trie()
    reversed_trie = Trie()

    for word in words:
        trie.insert(word)
        reversed_trie.insert(word[::-1])

    for query in queries:
        temp = 0
        if query[0] == '?':
            temp = len(reversed_trie.starts_with(query[::-1]))
        else:
            temp = len(trie.starts_with(query))

        answer.append(temp)

    return answer


# 효율성 테스트
# 테스트 1 〉	실패 (시간 초과)
# 테스트 2 〉	실패 (시간 초과)
# 테스트 3 〉	실패 (시간 초과)
# 테스트 4 〉	통과 (696.31ms, 13.4MB)
# 테스트 5 〉	통과 (696.88ms, 13.6MB)
def solution_fail(words, queries):
    answer = []

    for query in queries:
        result = 0

        for word in words:
            # 길이가 다르면 Fail
            if len(word) != len(query):
                continue

            flag = True
            for i in range(len(word)):
                if query[i] == '?':
                    continue

                # 중간에 하나라도 다르면 Fail
                if query[i] != word[i]:
                    flag = False
                    break

            # 길이도 같고, ?를 제외한 모든 글자가 같을 때 성공
            if flag:
                result += 1

        answer.append(result)

    return answer


sample_words = ["frodo", "front", "frost", "frozen", "frame", "kakao"]
sample_queries = ["fro??", "????o", "fr???", "fro???", "pro?"]
print(solution(sample_words, sample_queries))

579bfe6580fef71fb6e4ed0d4180ee2f63a6bdf5
class Node(object):
    <mask token>


class Trie(object):

    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        curr_node = self.head
        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            curr_node = curr_node.children[char]
        curr_node.data = string

    def search(self, string):
        curr_node = self.head
        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return False
        if curr_node.data is not None:
            return True

    def starts_with(self, query):
        curr_node = self.head
        result = []
        subtrie = None
        prefix = ''
        for char in query:
            if char != '?':
                prefix += char
        for char in prefix:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
                subtrie = curr_node
            else:
                return result
        queue = list(subtrie.children.values())
        while queue:
            curr = queue.pop()
            if curr.data is not None and len(curr.data) == len(query):
                result.append(curr.data)
            queue += list(curr.children.values())
        return result


<mask token>

class Node(object):

    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}


class Trie(object):

    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        curr_node = self.head
        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            curr_node = curr_node.children[char]
        curr_node.data = string

    def search(self, string):
        curr_node = self.head
        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return False
        if curr_node.data is not None:
            return True

    def starts_with(self, query):
        curr_node = self.head
        result = []
        subtrie = None
        prefix = ''
        for char in query:
            if char != '?':
                prefix += char
        for char in prefix:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
                subtrie = curr_node
            else:
                return result
        queue = list(subtrie.children.values())
        while queue:
            curr = queue.pop()
            if curr.data is not None and len(curr.data) == len(query):
                result.append(curr.data)
            queue += list(curr.children.values())
        return result


<mask token>

class Node(object):

    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}


class Trie(object):

    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        curr_node = self.head
        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            curr_node = curr_node.children[char]
        curr_node.data = string

    def search(self, string):
        curr_node = self.head
        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return False
        if curr_node.data is not None:
            return True

    def starts_with(self, query):
        curr_node = self.head
        result = []
        subtrie = None
        prefix = ''
        for char in query:
            if char != '?':
                prefix += char
        for char in prefix:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
                subtrie = curr_node
            else:
                return result
        queue = list(subtrie.children.values())
        while queue:
            curr = queue.pop()
            if curr.data is not None and len(curr.data) == len(query):
                result.append(curr.data)
            queue += list(curr.children.values())
        return result


def solution(words, queries):
    answer = []
    trie = Trie()
    reversed_trie = Trie()
    for word in words:
        trie.insert(word)
        reversed_trie.insert(word[::-1])
    for query in queries:
        temp = 0
        if query[0] == '?':
            temp = len(reversed_trie.starts_with(query[::-1]))
        else:
            temp = len(trie.starts_with(query))
        answer.append(temp)
    return answer


def solution_fail(words, queries):
    answer = []
    for query in queries:
        result = 0
        for word in words:
            if len(word) != len(query):
                continue
            flag = True
            for i in range(len(word)):
                if query[i] == '?':
                    continue
                if query[i] != word[i]:
                    flag = False
                    break
            if flag:
                result += 1
        answer.append(result)
    return answer


<mask token>

class Node(object):

    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}


class Trie(object):

    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        curr_node = self.head
        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)
            curr_node = curr_node.children[char]
        curr_node.data = string

    def search(self, string):
        curr_node = self.head
        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return False
        if curr_node.data is not None:
            return True

    def starts_with(self, query):
        curr_node = self.head
        result = []
        subtrie = None
        prefix = ''
        for char in query:
            if char != '?':
                prefix += char
        for char in prefix:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
                subtrie = curr_node
            else:
                return result
        queue = list(subtrie.children.values())
        while queue:
            curr = queue.pop()
            if curr.data is not None and len(curr.data) == len(query):
                result.append(curr.data)
            queue += list(curr.children.values())
        return result


def solution(words, queries):
    answer = []
    trie = Trie()
    reversed_trie = Trie()
    for word in words:
        trie.insert(word)
        reversed_trie.insert(word[::-1])
    for query in queries:
        temp = 0
        if query[0] == '?':
            temp = len(reversed_trie.starts_with(query[::-1]))
        else:
            temp = len(trie.starts_with(query))
        answer.append(temp)
    return answer


def solution_fail(words, queries):
    answer = []
    for query in queries:
        result = 0
        for word in words:
            if len(word) != len(query):
                continue
            flag = True
            for i in range(len(word)):
                if query[i] == '?':
                    continue
                if query[i] != word[i]:
                    flag = False
                    break
            if flag:
                result += 1
        answer.append(result)
    return answer


sample_words = ['frodo', 'front', 'frost', 'frozen', 'frame', 'kakao']
sample_queries = ['fro??', '????o', 'fr???', 'fro???', 'pro?']
print(solution(sample_words, sample_queries))

# trie 자료구조 사용
# https://blog.ilkyu.kr/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%97%90%EC%84%9C-Trie-%ED%8A%B8%EB%9D%BC%EC%9D%B4-%EA%B5%AC%ED%98%84%ED%95%98%EA%B8%B0
class Node(object):
    def __init__(self, key, data=None):
        self.key = key
        self.data = data
        self.children = {}


class Trie(object):
    def __init__(self):
        self.head = Node(None)

    def insert(self, string):
        curr_node = self.head

        for char in string:
            if char not in curr_node.children:
                curr_node.children[char] = Node(char)

            curr_node = curr_node.children[char]

        curr_node.data = string

    def search(self, string):
        curr_node = self.head

        for char in string:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
            else:
                return False

        if curr_node.data is not None:
            return True

    def starts_with(self, query):
        curr_node = self.head
        result = []
        subtrie = None

        prefix = ""
        for char in query:
            if char != '?':
                prefix += char

        # 트라이에서 prefix 를 찾고,
        # prefix의 마지막 글자 노드를 subtrie로 설정
        for char in prefix:
            if char in curr_node.children:
                curr_node = curr_node.children[char]
                subtrie = curr_node
            else:
                return result

        # bfs 로 prefix subtrie를 순회하며
        # data가 있는 노드들(=완전한 단어)를 찾는다.
        queue = list(subtrie.children.values())

        while queue:
            curr = queue.pop()
            if curr.data is not None and len(curr.data) == len(query):
                result.append(curr.data)

            queue += list(curr.children.values())

        return result


# 효율성 테스트
# 테스트 1 〉	실패 (시간 초과)
# 테스트 2 〉	실패 (시간 초과)
# 테스트 3 〉	실패 (런타임 에러)
# 테스트 4 〉	실패 (시간 초과)
# 테스트 5 〉	통과 (5497.76ms, 787MB)
def solution(words, queries):
    answer = []

    trie = Trie()
    reversed_trie = Trie()

    for word in words:
        trie.insert(word)
        reversed_trie.insert(word[::-1])

    for query in queries:
        temp = 0
        if query[0] == '?':
            temp = len(reversed_trie.starts_with(query[::-1]))
        else:
            temp = len(trie.starts_with(query))

        answer.append(temp)

    return answer


# 효율성 테스트
# 테스트 1 〉	실패 (시간 초과)
# 테스트 2 〉	실패 (시간 초과)
# 테스트 3 〉	실패 (시간 초과)
# 테스트 4 〉	통과 (696.31ms, 13.4MB)
# 테스트 5 〉	통과 (696.88ms, 13.6MB)
def solution_fail(words, queries):
    answer = []

    for query in queries:
        result = 0

        for word in words:
            # 길이가 다르면 Fail
            if len(word) != len(query):
                continue

            flag = True
            for i in range(len(word)):
                if query[i] == '?':
                    continue

                # 중간에 하나라도 다르면 Fail
                if query[i] != word[i]:
                    flag = False
                    break

            # 길이도 같고, ?를 제외한 모든 글자가 같을 때 성공
            if flag:
                result += 1

        answer.append(result)

    return answer


sample_words = ["frodo", "front", "frost", "frozen", "frame", "kakao"]
sample_queries = ["fro??", "????o", "fr???", "fro???", "pro?"]
print(solution(sample_words, sample_queries))
