[LeetCode] 211번 Design Add and Search Words Data Structure 문제를 풀어보았다. (ft. java)

2023년 03월 19일 일요일 - T1 가보자고!!

오늘 올려볼 문제는 211번 Design Add and Search Words Data Structure 이라는 문제이다.

사진을 클릭하면 해당 문제로 이동합니다.

오늘도 LeetCode 사이트 오늘의 문제를 가지고 왔다.

요즘 구현문제가 많네?

입력

이 문제는 입력을 설명하기 힘들다 문제를 참고해주길 바란다.

---

풀이 및 코드

WordDictionary라는 자료구조를 디자인하고 구현하는 문제이다.

addWord 메소드를 통해서 단어 저장이 가능하고 search 메소드를 통해서 단어 저장 여부를 알 수 있다.

이 때 search로 들어오는 단어는 '.'을 포함하고 있을 수 있고 이 '.'은 모든 문자로 대체 가능하다.

오늘은 처음부터 정답을 생각해냈다.

이전에 구현했었던 Trie를 사용해서 문제를 풀었다.

이제 코드를 봐보자!

풀이코드

class WordDictionary {
    Trie trie = new Trie();
    
    public void addWord(String word) {
        trie.insert(word);
    }
    
    public boolean search(String word) {
        return trie.find(word);
    }
}

class Trie {
    Trie[] tries = new Trie[26];
    boolean isEnd = false;
    
    public void insert(String word) {
        var trie = this;
        for(var c : word.toCharArray()) {
            int index = c - 'a';
            if(trie.tries[index] == null) trie.tries[index] = new Trie();
            trie = trie.tries[index];
        }
        trie.isEnd = true;
    }
    
    public boolean find(String word) {
        if(word.isEmpty()) return isEnd;
        
        var c = word.charAt(0);
        
        if(c == '.') {
            for(int i = 0; i < tries.length; i++) 
                if(tries[i] != null && tries[i].find(word.substring(1))) return true;
            
            return false;
        } 
        
        return tries[c - 'a'] != null && tries[c - 'a'].find(word.substring(1));
    }
}

---

제출 화면

요즘 구현문제가 많아서 클린 코드를 연습하기 좋은 것 같다.

내일도 문제를 풀어서 블로그에 글을 쓸 수 있으면 좋겠다.