Java, LeetCode | 212. Word Search 2

🚀 풀이 후기

Trie 문제를 처음 풀어봤습니다.

Trie의 원리만 알고 있다면 쉽게 풀 수 있을 것 같습니다.

class Trie {
    public Trie[] trie;
    public boolean flag;

    public Trie() {
        trie = new Trie[26];
        flag = false;
    }

    public void insert(String word) {
        Trie node = this;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.trie[index] == null) {
                node.trie[index] = new Trie();
            }
            node = node.trie[index];
        }
        node.flag = true;
    }

    public boolean search(String word) {
        Trie node = this;
        for (char ch : word.toCharArray()) {
            int index = ch - 'a';
            if (node.trie[index] == null) {
                return false;
            }
            node = node.trie[index];
        }
        return node.flag;

    }

    public boolean startsWith(String prefix) {
        Trie node = this;
        for (char ch : prefix.toCharArray()) {
            int index = ch - 'a';
            if (node.trie[index] == null) {
                return false;
            }
            node = node.trie[index];
        }
        return true;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

🌒 문제 설명

문자가 적혀있는 char[][] board 2차원 배열에서 words 중 찾은 단어 List를 반환하는 문제입니다.

board에서 다음 문자를 찾을 때에는 상, 하, 좌, 우로 인접해 있는 곳을 가야 합니다.

Given an m x n board of characters and a list of strings words, 
return all words on the board.

Each word must be constructed from letters of sequentially adjacent cells, 
where adjacent cells are horizontally or vertically neighboring. 
The same letter cell may not be used more than once in a word.

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

 

Example 1 그림

Example 1:

Input: board = [["o","a","a","n"],
                ["e","t","a","e"],
                ["i","h","k","r"],
                ["i","f","l","v"]], 
words = ["oath","pea","eat","rain"]

Output: ["eat","oath"]

 

Example 2 그림

Example 2:

Input: board = [["a","b"],
                ["c","d"]], 
words = ["abcb"]

Output: []

🌓 문제 풀이

class Solution {
    public Trie trie = new Trie();
    public List<String> found; // 발견한 문자 목록
    public int[][] move = {
            { 0, 1 }, // 우
            { 0, -1 }, // 좌
            { 1, 0 }, // 하
            { -1, 0 } // 상
    };
    public char[][] map; // 문자가 저장된 2차원 배열
    public boolean[][] visited; // 방문 체크

    public List<String> findWords(char[][] board, String[] words) {
        found = new ArrayList<>();
        makeTrie(words); // trie에 words들을 저장합니다.
        map = board;

        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[0].length; x++) {
                String prefix = board[y][x] + "";
                
                // trie에 해당 문자가 존재하는지 확인합니다.
                if (trie.startsWith(prefix)) {
                    // 존재한다면 방문체크할 2차원 배열을 초기화하고, 단어를 찾으러 갑니다.
                    visited = new boolean[board.length][board[0].length];
                    findWord(y, x, prefix, trie.node[board[y][x] - 'a']);
                }
            }
        }
        return found; // 발견한 문자 목록을 반환합니다.
    }

    public void findWord(int y, int x, String prefix, Trie now) {
        // System.out.println("y: " + y + ", x: " + x);
        // System.out.println("prefix: " + prefix);
        // System.out.println("flag: " + now.flag);
        // System.out.println("trie now: " + Arrays.toString(now.node));
        
        // 단어를 다 찾았다면 found에 추가하고, 현재 trie에 찾았다고 표시합니다.
        if (now.flag) {
            found.add(prefix);
            now.flag = false;
        }
        
        // map에 방문했음을 체크합니다.
        visited[y][x] = true;
        for (int i = 0; i < 4; i++) {
            // 상, 하, 좌, 우를 순환하면서 방문하지 않았고, map의 범위를 넘어가지 않은 좌표를 찾습니다.
            int ny = y + move[i][0];
            int nx = x + move[i][1];
            if (ny < 0 || nx < 0 || ny >= map.length || nx >= map[0].length || visited[ny][nx]) {
                continue;
            }
            
            // 찾은 좌표를 이용해서 다음 문자를 ch변수에 세팅합니다.
            char ch = map[ny][nx];
            String word = prefix + ch;
            
            // trie에 다음 문자가 없으면 다시 찾습니다.
            if (!now.startsWith(ch + "")) {
                continue;
            }
            
            // 찾은 문자를 이용해서 재귀함수 안으로 들어갑니다.
            findWord(ny, nx, word, now.node[ch - 'a']);
        }
        // 탐색을 중단하기 때문에 방문 기록을 false로 돌려놓습니다.
        visited[y][x] = false;
    }

    public void makeTrie(String[] words) {
        for (String word : words) {
            trie.insert(word);
        }
    }

    public class Trie {
        public Trie[] node;
        public boolean flag;

        public Trie() {
            node = new Trie[26];
            flag = false;
        }

        public void insert(String word) {
            Trie trie = this;
            for (char ch : word.toCharArray()) {
                int index = ch - 'a';
                if (trie.node[index] == null) {
                    trie.node[index] = new Trie();
                }
                trie = trie.node[index];
            }
            trie.flag = true;
        }

        public boolean search(String word) {
            Trie trie = this;
            for (char ch : word.toCharArray()) {
                int index = ch - 'a';
                if (trie.node[index] == null) {
                    return false;
                }
            }
            return trie.flag;
        }

        public boolean startsWith(String prefix) {
            Trie trie = this;
            for (char ch : prefix.toCharArray()) {
                int index = ch - 'a';
                if (trie.node[index] == null) {
                    return false;
                }
            }
            return true;
        }
    }
}

- 시간복잡도: O(M*N*10^4*10)

- 공간복잡도: O(M*N+26*10^4*10)

🌕 리팩토링

Trie를 배열이 아닌 HashMap으로 구현했습니다.

그리고 검색 완료한 단어를 Trie에서 제거해서 다음 검색을 더 빠르게 했습니다.

class Trie {
    HashMap<Character, Trie> child;
    String word; // 찾으려는 단어

    public Trie() {
        child = new HashMap<>();
        word = null;
    }
}

class Solution {
    public char[][] map;
    public boolean[][] visited; // 방문체크 배열
    public List<String> found; // 발견한 단어 목록
    public Trie root;
    public int[][] move = {
            { 0, 1 }, // 우
            { 0, -1 }, // 좌
            { 1, 0 }, // 하
            { -1, 0 } // 상
    };

    public List<String> findWords(char[][] board, String[] words) {
        map = new char[board.length][board[0].length]; // board 2차원 배열을 복사한 map
        visited = new boolean[board.length][board[0].length]; // 방문체크 배열 초기화
        found = new ArrayList<>();
        root = new Trie();
        for (int i = 0; i < board.length; i++) {
            map[i] = Arrays.copyOf(board[i], board[0].length);
        }

        makeTrie(words); // Trie에 단어를 넣습니다.
        for (int y = 0; y < board.length; y++) {
            for (int x = 0; x < board[0].length; x++) {
                char ch = board[y][x];
                if (root.child.containsKey(ch)) { // trie에 있는 첫 문자이면 단어를 찾으러 갑니다.
                    dfs(y, x, root.child.get(ch));
                }
            }
        }
        return found; // 발견한 단어 목록을 반환합니다.

    }

    public void makeTrie(String[] words) {
        for (String word : words) {
            Trie node = root;
            for (Character ch : word.toCharArray()) {
                if (!node.child.containsKey(ch)) {
                    node.child.put(ch, new Trie());
                }
                node = node.child.get(ch);
            }
            node.word = word;
        }
    }

    public void dfs(int y, int x, Trie parent) {
        // System.out.println("y: " + y + ", x: " + x);
        // System.out.println("Trie word: " + parent.word);
        // System.out.println("Trie child: " + parent.child.keySet());
        visited[y][x] = true;
        if (parent.word != null) {
            found.add(parent.word);
            parent.word = null;
        }

        for (int i = 0; i < 4; i++) {
            int ny = y + move[i][0];
            int nx = x + move[i][1];
            if (ny < 0 || nx < 0 || ny >= map.length || nx >= map[0].length || visited[ny][nx]) {
                continue;
            }
            char ch = map[ny][nx];
            if (!parent.child.containsKey(ch)) {
                continue;
            }
            Trie children = parent.child.get(ch);
            dfs(ny, nx, children);
            
            // 자식 노드가 없으면 현재 문자를 Trie에서 제거합니다.
            if (children.child.size() == 0) {
                parent.child.remove(ch);
            }
        }
        visited[y][x] = false;
    }
}

- 시간복잡도: O(M*N*10^4*10)

- 공간복잡도: O(M*N+10^4*10)

 

---

리트코드 문제

깃허브 코드