기술 기사

트라이(trie, "트라이"로 발음) 또는 접두사 트리는 문자열 데이터 세트에서 키를 효율적으로 저장하고 검색하는 데 사용되는 트리 데이터 구조입니다. 이 데이터 구조는 자동완성이나 맞춤법 검사기 등 다양한 용도로 사용됩니다.

Trie 클래스를 구현합니다.

Trie()는 trie 객체를 초기화합니다.
void insert(String word) 문자열 word를 트라이에 삽입합니다.
int countWordsEqualTo(String word) 트라이에서 문자열 word의 인스턴스 수를 반환합니다.
int countWordsStartingWith(String prefix) 문자열 접두사를 접두사로 갖는 트라이의 문자열 개수를 반환합니다.
void erase(String word) 트라이에서 문자열 word를 지웁니다.

'(', ')', '{', '}', '[', ']' 문자만 포함된 문자열이 주어졌을 때 입력 문자열이 유효한지 판별합니다.

입력 문자열은 다음과 같은 경우 유효합니다.

열린 괄호는 같은 유형의 괄호로 닫아야 합니다.
열린 괄호는 올바른 순서로 닫아야 합니다.
모든 닫힌 괄호에는 같은 유형의 열린 괄호가 대응됩니다.

문자로 구성된 mxn 보드와 단어 문자열 목록이 주어졌을 때, 보드에 있는 모든 단어를 반환합니다.

각 단어는 연속적으로 인접한 셀의 문자로 구성되어야 하며, 인접한 셀은 수평 또는 수직으로 이웃해야 합니다. 동일한 문자 셀은 단어에서 두 번 이상 사용될 수 없습니다.

새로운 단어를 추가하고 문자열이 이전에 추가된 문자열과 일치하는지 확인하는 데이터 구조를 설계합니다.

WordDictionary 클래스를 구현합니다.

WordDictionary() 객체를 초기화합니다.
void addWord(word) 데이터 구조에 단어를 추가합니다. 나중에 일치시킬 수 있습니다.
bool search(word) 데이터 구조에 word와 일치하는 문자열이 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다. 단어에는 점이 포함될 수 있습니다. 점은 모든 문자와 일치할 수 있습니다.

트라이(trie, "트라이"로 발음) 또는 접두사 트리는 문자열 데이터 세트에서 키를 효율적으로 저장하고 검색하는 데 사용되는 트리 데이터 구조입니다. 이 데이터 구조는 자동완성이나 맞춤법 검사기 등 다양한 용도로 사용됩니다.

Trie 클래스를 구현합니다.

Trie()는 trie 객체를 초기화합니다.
void insert(String word) 문자열 word를 트라이에 삽입합니다.
boolean search(문자열 단어) 문자열 단어가 트라이에 있는 경우(즉, 이전에 삽입된 경우) true를 반환하고, 그렇지 않은 경우 false를 반환합니다.
boolean startsWith(String prefix) 이전에 삽입된 문자열 단어에 접두사 prefix가 포함되어 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

이진 검색 트리(BST)가 주어졌을 때, BST에서 주어진 두 노드의 가장 낮은 공통 조상(LCA) 노드를 찾으세요.

위키피디아의 LCA 정의에 따르면 "최저 공통 조상은 두 노드 p와 q 사이에서 정의되며, p와 q를 모두 자손으로 갖는 T의 가장 낮은 노드로 정의됩니다(여기서 노드는 자기 자신의 자손이 될 수 있습니다)."

이진 검색 트리의 루트와 정수 k가 주어지면, 트리에 있는 모든 노드의 값 중 k번째로 작은 값(1부터 색인)을 반환합니다.

이진 트리의 루트가 주어졌을 때, 그것이 유효한 이진 검색 트리(BST)인지 판별해보세요.

유효한 BST는 다음과 같이 정의됩니다.

노드의 왼쪽 서브 트리에는 해당 노드의 키보다 작은 키를 가진 노드만 포함됩니다.
노드의 오른쪽 서브 트리에는 노드의 키보다 큰 키를 가진 노드만 포함됩니다.
왼쪽과 오른쪽 서브트리도 모두 이진 검색 트리여야 합니다.