Design and implement an LRU (Least Recently Used) cache. The cache should support two operations: get(key) and put(key, value). Both operations must run in O(1) time on average. If the cache exceeds its capacity, the least recently used key should be evicted.
You are tasked with creating a data structure that allows adding words and checking if a word matches any previously added word, with support for the wildcard ‘.’ character.
Design and implement a queue using only two stacks. The queue should support the basic operations of a normal queue: enqueue, dequeue, peek, and checking if the queue is empty.