리트코드 - 211. Design Add and Search Words Data Structure

리트코드 - 211. Design Add and Search Words Data Structure

출처 - https://leetcode.com/problems/design-add-and-search-words-data-structure/?envType=study-plan-v2&envId=top-interview-150

 

문제 설명

새로운 단어를 추가할 수 있고 이전에 추가된 단어 중에서 주어진 문자열과 일치하는 것이 있는 데이터 구조를 만드세요.

 

WordDictionary" 클래스를 구현하세요:

- WordDictionary() :객체를 초기화합니다.

- addWord(word) : 단어를 데이터 구조에 추가할 수 있으며, 나중에 이 단어와 일치 여부를 확인할 수 있습니다.

- search(word) : 데이터 구조에 있는 문자열 중에서 주어진 단어와 일치하는 것이 있는지 확인하며, '.' (도트) 문자는 어떤 문자와도 일치할 수 있어야 합니다. 이 메서드는 일치하는 문자열이 있으면 true를 반환하고, 그렇지 않으면 false를 반환해야 합니다.

 

의사코드

class Node     Map children     boolean isEndOfWord     생성자         children = new HashMap         isEndOfWord = false class Trie     Node root     생성자         root = new Node     addWord 메소드(word)         if (word 길이 == 0)             함수 빠져나옴         현재Node = this.root         반복문 시작 (word의 각 문자 하나씩)             if (현재Node의 children에 c가 없다면)                 자식노드 = children에서 c 자식 노드 가져옴                 if (자식Node == null)                     자식Node = new Node                     현재 Node의 children에서 c에 해당하는 Node로 갱신                               현재Node = 자식Node         반복문 종료         현재Node의 isEndOfWord를 true로 설정     search 메소드(word)         searchNode(this.root, word) 메서드 호출하여 리턴     searchRecursive 메소드(node, word)         if (word 길이 == 0)             node의 isEndOfWord 리턴         c = word의 첫번째 문자열         if (c == '.')             반복문 시작 (node의 children의 value값(childrenNode)을 순회)                 if ( searchRecursive메소드 (childrenNode, word에서 앞글자 빼고 남은 값) 재귀적 호출)                     true 리턴                 false 리턴             반복문 종료                 else                 자식Node = 현재Node의 children에서 c에 해당하는 자식Node를 가져옴             if (childrenNode = null)                 searchRecursive메소드 (childrenNode, word에서 앞글자 빼고 남은 값) 재귀적 호출값 리턴                 false 리턴

 

풀이코드

public class Node {
    Map<Character, Node> children;
    boolean isEndOfWord;

    public Node() {
        this.children = new HashMap<>();
        this.isEndOfWord = false;
    }
}


class WordDictionary {
    Node root;

    public WordDictionary() {
        this.root = new Node();
    }
    
    public void addWord(String word) {
        if (word.length() == 0) {
            return;
        }
        Node currentNode = this.root;

        for (char c : word.toCharArray()) {
            Node childrenNode = currentNode.children.get(c);

            if (childrenNode == null) {
                childrenNode = new Node();
                currentNode.children.put(c, childrenNode);
            }

            currentNode = childrenNode;
        }

        currentNode.isEndOfWord = true;
    }
    
    public boolean search(String word) {
        return searchRecursive(this.root, word);
    }

    private boolean searchRecursive(Node node, String word) {
        if (word.length() == 0) {
            return node.isEndOfWord;
        }

        char c = word.charAt(0);

        if (c == '.') {
            for (Node childrenNode : node.children.values()) {
                if (searchRecursive(childrenNode, word.substring(1))) {
                    return true;
                }
            }
        } else {
            Node childrenNode = node.children.get(c);
            if (childrenNode != null) {
                return searchRecursive(childrenNode, word.substring(1));
            }
        }
        return false;
    }
}

코드설명

trie 자료구조를 활용한 문제로 이전 문제와 기본적인 설명은 같다.

이전 포스팅에 trie 자료구조에 대해 그림으로 자세하게 설명해놓았으니 trie에 대한 이해가 필요하다면 해당 게시물을 참고.

 

위 문제에서는 addWord 메소드에서는 파라미터 word를 배열로 만들어 입력했고,

search메소드에서는 searchRecursive 메소드를 만들어 파라미터로 node값과 word값을 받아서 재귀적으로 구현했다.

 

addWord 메소드는 word를 Character배열로 만들고 현재 노드를 root로 만든다음,

자식Node를 확인하여 null값을 가지면 key값, value=자식노드를 추가해준다.

마지막 값에는 단어의 끝임을 알리는 isEndOfWord 값을 true로 해준다.

 

searchRecursive 메소드에서는 재귀적으로 구현했는데 과정을 그림으로 적어보면 이렇다.

문제에서 "."은 모든 문자열을 포함하는 문자열이므로

string이 "." 인지 아닌지를 확인해서 "."이면 다음Node에 모든 값을 전체적으로 쫙 펼쳐서 각각 값을 확인해야하고,

"." 이 아니라면 다음문자열에 대해서 Node값을 가지는지 확인하기 위해 searchRecursive메소드를 호출한다.

 

예를 들어 "a."라는 값을 검색하고자 한다면, 지난번 포스팅 root를 다시 예시로 들겠다.

먼저 문자열 a를 확인하는데 a는 "."이 아니므로 a노드로 초점을 맞추고, 이 노드를 기준으로 searchRecursive메소드를 호출한다.

또한 앞 문자열 a는 확인했으니 지워야 한다.

다음으로 확인할 문자열이 "." 이므로, a의 자식Node 에 대해서 모두 검색을 해야 한다.

1) 먼저 b이다.

b는 "." 이 아니므로 똑같이 b를 Node로 하여 다시 searchRecursive메소드를 호출한다.

다음 문자열도 지워지므로 ""가 되는데, 이 때 b인 Node는 단어의 끝이 아니니 false를 리턴한다.

하지만 아직 c를 검색하지 않았다.

 

2) c를 검색한다.

c는 "."이 아니므로 c를 Node로 하여 searchRecursive메소드를 호출한다.

다음 문자열도 지워지므로 ""가 되는데 이때 단어의 끝이 보이므로 true를 리턴한다.

 

if (c == '.') {
    for (Node childrenNode : node.children.values()) {
        if (searchRecursive(childrenNode, word.substring(1))) {
            return true;
        }
    }
}

단순하게 searchRecursive를 return 해버리면 b만 조회하고 false를 리턴해버리지만,

이렇게 if문을 감싸면 true일때만 true를 리턴한다.

 

모든 분기를 거치고 true를 만나지 못하면 false를 리턴하게 만든다.

 

시간복잡도 - O(n) (n은 입력되는 단어의 길이, search 메소드의 경우 최악의 경우 O(26^n) 26은 알파벳 갯수)

공간복잡도 - O(m) (m은 trie의 깊이)

 

문제를 풀며 생각한 흐름과 배운 점

trie노드 문제를 풀고 시간복잡도를 정리하여 생각할 때쯤 되니 search 메소드가 너무 비효율적이었다.

그래서 이전 문제에서 Map대신 배열을 활용했던 것처럼 배열을 이용해보기로 했다.

 

1차 개선

public class Node {
    Node[] children;
    boolean isEndOfWord;

    public Node() {
        this.children = new Node[26]; // 배열로 변경
        this.isEndOfWord = false;
    }
}


class WordDictionary {
    Node root;

    public WordDictionary() {
        this.root = new Node();
    }
    
    public void addWord(String word) {
        if (word.length() == 0) {
            return;
        }
        Node currentNode = this.root;

        for (char c : word.toCharArray()) {  // 배열에 넣는 방식으로 변경
            int idx = c - 'a';   // 배열 인덱스 찾기
            if (currentNode.children[idx] == null) {
                currentNode.children[idx] = new Node();
            }
            currentNode = currentNode.children[idx];
        }
        currentNode.isEndOfWord = true;
    }
    
    public boolean search(String word) {
        return searchRecursive(this.root, word);
    }

    private boolean searchRecursive(Node node, String word) {
        if (word.length() == 0) {
            return node != null && node.isEndOfWord;
        }

        if (node == null) {
            return false;
        }

        char c = word.charAt(0);
        int idx = c - 'a';
        if (c == '.') {
            for (Node childrenNode : node.children) {
                if (searchRecursive(childrenNode, word.substring(1))) {
                    return true;
                }
            }
        } else {
            Node childrenNode = node.children[idx];
            if (childrenNode != null) {
                return searchRecursive(childrenNode, word.substring(1));
            }
        }
        return false;
    }
}

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

children을 map형태로 가지고 있으면 key값으로 빠르게 찾아올 수 있지만, 이 경우에는 알파벳 26개만 저장하는 배열로 만들면 인덱스값만 알고 있으면 map보다 빠르게 접근이 가능하다.

 

int idx = c - 'a'를 적용하여 0번부터 25번까지 순서에 맞게 노드가 들어가게 insert하고, 재귀형태로 탐색은 동일하게 한다.

if (c == '.') {
    for (Node childrenNode : node.children) {
        if (searchRecursive(childrenNode, word.substring(1))) {
            return true;
        }
    }
}

if (word.length() == 0) {
    return node != null && node.isEndOfWord;
}

단, 와일드카드가 주어졌을 때 모든 값을 순회할 때 children 배열중에서 null 값을 가진 배열도 있기 때문에 단어의 크기가 0이었을 때 node가 null인지 확인해주어야 isEndOfWord에서 NPE가 나지 않는다.

 

2차개선

이렇게 코드를 테스트 하고보니 굳이 children 배열을 다 순회해야 하나 싶었다.

처음부터 null 값이 있으면 순회를 안하면 되는게 아닌가 싶어 코드를 수정했고, 확실히 빨라졌다.

 

if (c == '.') {
    for (Node childrenNode : node.children) {
        if (childrenNode != null && searchRecursive(childrenNode, word.substring(1))) {
            return true;
        }
    }
}

if (word.length() == 0) {
    return node.isEndOfWord;
}

 

 

정리

trie노드에 들어가는 값이 한정적일 때에는 배열을 사용하는 것이 효율적이다.