사전의 단어 개수가 N(10^4 이하), 사전에 특정 단어가 존재하는지 질문의 개수가 M(10^4 이하), 모든 단어의 길이는 최대 500(=L)

1. trie 만들어서 풀기. O((N+M)L) → python 3 : 5.0초

2. 각 쿼리 단어 y에 대해 x in 사전 식으로 비교해서 풀기. O(NML) → python 3 : 2.5초

이렇게 수행시간이 측정되니 의문이 생깁니다.

파이썬에서 두 문자열이 같은지 비교하는 연산은 O(길이)라고 알고 있는데, 그럼 'x in 사전'이 데이터가 약해서 빨리 수행된 것인지 궁금하네요.

trie를 만드는 데 수행시간이 조금 걸리는 것은 충분히 이해가 되는데, 2번이 생각보다 너무 빨리 수행되서 신기합니다.

도움주시면 감사하겠습니다.