[NeetCode-LeetCode] Design Add and Search Words Data Structure JAVA

반응형

728x90

[NeetCode-LeetCode] Design Add and Search Words Data Structure - Medium 

---

접근

• 접근 방법

---

풀이

단어 추가와 검색을 가능이 가능한 데이터 구조를 디자인하는 문제이다. 단어 추가의 경우 입력받는 단어를 데이터 구조 내 저장하는 로직을 수행하고 검색의 경우 데이터 구조 검색하고자 하는 단어가 저장되어 있는지 확인하는 로직이다. trie 파트에 있는 문제로 trie를 사용하여 풀어야 하는 문제로 전에 풀었던 문제는 검색 단어가 그대로 주어졌기 때문에 특별히 신경 쓸 부분이 없었지만 이번에는 "." 점의 형태로 패턴 매칭을 수행해야 하기 때문에 좀 더 복잡해졌다고 볼 수 있다.

 

기존 삽입 부분과 베이스는 이전에 풀었던 코드를 그대로 들고왔다. 

class Node {
    public Node[] child;
    private boolean endFlag;

    public Node() {
        this.child = new Node[26];
        this.endFlag = false;
    }

    public void end() {
        this.endFlag = true;
    }

    public boolean isEnd() {
        return endFlag;
    }
}

trie는 단어를 문자 단위로 쪼개 트리 기반의 구조로 저장하게 되므로 트리의 역할을 해 줄 Node 클래스이다. endFlag를 통해 단어의 끝을 표시하게 된다. ban, banana라는 단어가 저장되어 있는 경우 ban까지의 경로는 두 단어가 동일하기 때문에 문자 n에 endFlag를 표시하여 ban이라는 단어도 저장되어 있음을 나타내는 것이다.

class WordDictionary {
    private Node trie;

    public WordDictionary() {
        trie = new Node();
    }

    public void addWord(String word) {
        Node pointer = trie;

        for (int i = 0; i < word.length(); i++) {
            int n = word.charAt(i) - 'a';

            if (pointer.child[n] == null) {
                pointer.child[n] = new Node();
            }
            pointer = pointer.child[n];
        }

        pointer.end();
    }

생성자부터 삽입에 대한 코드이다. 삽입의 경우 문자 단위로 쪼개 트리 형태로 Node 클래스에 저장해준다.

    public boolean search(String word) {
        return searchDfs(word, trie, 0);
    }

    public boolean searchDfs(String word, Node current, int index) {
        if (word.length() == index) {
            return current.isEnd();
        }

        char c = word.charAt(index);
        if (c == '.') {
            for (int i = 0; i < 26; i++) {
                if (current.child[i] != null && searchDfs(word, current.child[i], index + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            int n = c - 'a';
            if (current.child[n] == null) {
                return false;
            }
            return searchDfs(word, current.child[n], index + 1);
        }
    }

검색을 하는 부분이다. 기본적으로 search 메서드의 파라미터와 형태가 고정되어 있기 때문에 재귀 형태로 탐색을 위해 새로운 메서드를 추가해 수행해 주었다. "."을 통한 패턴 매칭 때문에 dfs를 사용해 풀어주었다. 단어에 "." 이렇게 점이 들어가 있는 경우 모든 문자와 매칭 가능하기 때문에 해당 자리 문자가 "."이라면 26개의 문자가 모두 위치할 수 있기 때문에 재귀를 통해 매칭되는 문자가 있는지 검색하게 된다. "."이 아니라면 다음 경로에 문자가 있는지 확인하고 단어의 길이만큼 진행이 다 되었다면 endFlag 확인을 통해 해당 지점까지의 문자가 있는지 체크한다. 

trie

 

---

전체 코드

class WordDictionary {
    private Node trie;

    public WordDictionary() {
        trie = new Node();
    }

    public void addWord(String word) {
        Node pointer = trie;

        for (int i = 0; i < word.length(); i++) {
            int n = word.charAt(i) - 'a';

            if (pointer.child[n] == null) {
                pointer.child[n] = new Node();
            }
            pointer = pointer.child[n];
        }

        pointer.end();
    }

    public boolean search(String word) {
        return searchDfs(word, trie, 0);
    }

    public boolean searchDfs(String word, Node current, int index) {
        if (word.length() == index) {
            return current.isEnd();
        }

        char c = word.charAt(index);
        if (c == '.') {
            for (int i = 0; i < 26; i++) {
                if (current.child[i] != null && searchDfs(word, current.child[i], index + 1)) {
                    return true;
                }
            }
            return false;
        } else {
            int n = c - 'a';
            if (current.child[n] == null) {
                return false;
            }
            return searchDfs(word, current.child[n], index + 1);
        }
    }
}

class Node {
    public Node[] child;
    private boolean endFlag;

    public Node() {
        this.child = new Node[26];
        this.endFlag = false;
    }

    public void end() {
        this.endFlag = true;
    }

    public boolean isEnd() {
        return endFlag;
    }
}

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary obj = new WordDictionary();
 * obj.addWord(word);
 * boolean param_2 = obj.search(word);
 */