소프트웨어 기술 블로그

트라이(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는 다음과 같이 정의됩니다.

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

이진 트리의 전위 순회인 전위 순회와 같은 트리의 중위 순회인 중위 순회라는 두 개의 정수 배열인 전위 순회와 중위 순회가 주어지면, 이진 트리를 구성하여 반환합니다.

두 개의 이진 트리 root와 subRoot의 루트가 주어졌을 때, root의 서브 트리 중 subRoot와 같은 구조와 노드 값을 갖는 서브 트리가 있으면 true를 반환하고, 그렇지 않으면 false를 반환합니다.

이진 트리의 서브 트리는 트리의 노드와 이 노드의 모든 자손으로 구성된 트리입니다. 트리 트리는 그 자체의 서브트리로 간주될 수도 있습니다.

직렬화는 데이터 구조나 객체를 비트 시퀀스로 변환하여 파일이나 메모리 버퍼에 저장하거나 네트워크 연결을 통해 전송하여 나중에 같은 컴퓨터 환경이나 다른 컴퓨터 환경에서 재구성할 수 있는 프로세스입니다.

이진 트리를 직렬화하고 역직렬화하는 알고리즘을 설계합니다. 직렬화/역직렬화 알고리즘이 작동하는 방법에는 제한이 없습니다. 이진 트리를 문자열로 직렬화할 수 있고, 이 문자열을 원래 트리 구조로 역직렬화할 수 있는지 확인하기만 하면 됩니다.

설명: 입출력 형식은 LeetCode가 이진 트리를 직렬화하는 방식과 동일합니다. 반드시 이 형식을 따를 필요는 없으므로 창의력을 발휘하여 직접 다양한 접근 방식을 생각해 보세요.

이진 트리의 루트가 주어지면, 노드 값의 수준 순서 순회를 반환합니다. (즉, 왼쪽에서 오른쪽으로, 수준별로).

이진 트리의 경로는 노드의 시퀀스이며, 시퀀스에서 인접한 노드의 각 쌍은 그들을 연결하는 간선을 갖습니다. 노드는 시퀀스에서 최대 한 번만 나타날 수 있습니다. 경로가 루트를 통과할 필요는 없습니다.

경로의 경로 합은 경로에 있는 노드 값의 합입니다.

이진 트리의 루트가 주어지면 비어 있지 않은 모든 경로의 최대 경로 합계를 반환합니다.

이진 트리 T에 대해 다음과 같이 플립 연산을 정의할 수 있습니다. 아무 노드나 선택하고 왼쪽과 오른쪽 자식 서브 트리를 바꿉니다.

이진 트리 X가 이진 트리 Y와 플립 동치인 것은 몇 번의 플립 연산을 거친 후 X를 Y와 같게 만들 수 있는 경우에만 가능합니다.

두 이진 트리 root1과 root2의 루트가 주어졌을 때, 두 트리가 뒤집혀 동치이면 true를 반환하고 그렇지 않으면 false를 반환합니다.

두 이진 트리 p와 q의 근이 주어졌을 때, 두 근이 같은지 확인하는 함수를 작성하세요.

두 개의 이진 트리는 구조적으로 동일하고 노드의 값이 같으면 동일한 것으로 간주됩니다.

문자열 목록을 문자열로 인코딩하는 알고리즘을 설계하세요. 인코딩된 문자열은 네트워크를 통해 전송되고 디코딩되어 원래 문자열 목록으로 다시 반환됩니다.

문자열 s가 주어지면, 해당 문자열에 있는 팰린드롬 부분 문자열의 개수를 반환합니다.

문자열은 앞으로 읽든 뒤로 읽든 같을 때 팰린드롬입니다.

부분 문자열은 문자열 내에서 연속된 문자 시퀀스입니다.