208-트 리 구현(접두사 트 리)
접두사 트 리 는 우리 가 자주 사용 하 는 데이터베이스 색인 과 같은 자주 사용 하 는 데이터 구조 이다.그리고 접두사 나무 에 대한 소 개 는 LeetCode 중국 에 접두사 나무 에 관 한 튜 토리 얼 이 있 기 때문에 저 는 도끼 질 을 하지 않 겠 습 니 다.제 답 도 튜 토리 얼 의 방향 을 참고 하여 풀 겠 습 니 다.여러분 께 참고 가 되 기 를 바 랍 니 다.다음은 원제:
insert,search,starts With 세 동작 을 포함 하 는 Trie(접두사 트 리)를 실현 합 니 다.
예제:Trie trie=new Trie();
trie.insert("apple");trie.search("apple"); // truetrie.search("app")를 되 돌려 줍 니 다.//falsetrie.startsWith("app");/truetrie.insert("app")를 되 돌려 줍 니 다.trie.search("app"); // true 설명 을 되 돌려 줍 니 다:
너 는 모든 입력 이 소문 자 a-z 로 구성 되 어 있다 고 가정 할 수 있다.모든 입력 이 비 어 있 는 문자열 임 을 보증 합 니 다.
문제 풀이 의 사고 방향.
4.567917.나 무 는 노드 로 구성 되 어 있 습 니 다.노드 정 의 는 노드 값(접두사 트 리 의 정의,값 은 문자 char)과 잎 노드 의 지침 을 포함 해 야 합 니 다.그러나 한 단어 인지 아 닌 지 를 식별 하기 위해 boolean 변 수 를 추가 합 니 다
4.567917.전체 소문 자(a-z)로 입력 한 것 을 알 고 있 기 때문에 길이 가 26 인 배열 로 잎 노드 를 저장 할 수 있 습 니 다.또한 a-z 의 ASCII 코드 는 연속 적 이 고 ASCII 는 97-123 이기 때문에 ASCII 코드-97=대응 하 는 노드 의 배열 아래 표 시 를 직접 사용 할 수 있 습 니 다
배열 기반 접두사 트 리
class Trie {
/**
*
*/
public char value;
/**
* a-z 26 , a ASCII 97, ASCII -97
*/
public Trie[] children=new Trie[26];
/**
*
*/
public boolean endAsWord=false;
public Trie() {
}
/**
*
* @param word
*/
public void insert(String word) {
if(word!=null){
//
char[] charArr=word.toCharArray();
// ,
Trie currentNode=this;
for(int i=0;i
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
0부터 시작하는 LeetCode Day8 「1302. Deepest Leaves Sum」해외에서는 엔지니어의 면접에 있어서 코딩 테스트라고 하는 것이 행해지는 것 같고, 많은 경우, 특정의 함수나 클래스를 주제에 따라 실장한다고 하는 것이 메인이다. 빠른 이야기가 본고장에서도 행해지고 있는 것 같은 코...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.