[알고리즘문제] 릿코드 Word Search II

leetcode.com/problems/word-search-ii/

Word Search II - LeetCode

 

2차원 배열 board와 1차원 배열 words가 주어짐

board에서 words의 문자를 만들 수 있으면 해당 문자를 반환함

words는 board에서 상하좌우로 이어질 수 있고 이어져 있지 않다면 만들 수 없는 문자임

 

rust코드로 작성

use std::collections::HashMap;

#[derive(Default, Debug)]
struct Trie{
    node : HashMap<char, Trie>,
    word : String
}

impl Trie{
    fn new() -> Self{
        Default::default()
    }
    fn insert(&mut self, words: &Vec<String>){
        for word in words.iter(){
            let mut current_node = &mut *self;
            for c in word.chars(){
                //node의 hashmap에서 c가 없으면 hashmap에 Node를 insert
                current_node = current_node.node.entry(c).or_insert(Trie::new());
            }
            current_node.word = word.parse().unwrap();
        }
    }
}

impl Solution{
    pub fn find_words(board : Vec<Vec<char>>, words : Vec<String>) -> Vec<String>{
        let mut answer:Vec<String> = Vec::new();
        let mut trie = Trie::new();
        trie.insert(&words);
        println!("{:#?}", trie);
        let mut visited = board.clone();

        //2차원 배열 전체를 확인하기 위해
        for x in 0..visited.len() {
            for y in 0..visited[x].len() {
                Self::search_position(&mut visited, &mut answer, &mut trie, x, y);
            }
        }
        println!("{:?}", answer);
        answer
    }
    fn search_position(mut visited : &mut Vec<Vec<char>>, answer : &mut Vec<String>, trie : &mut Trie, x: usize, y: usize) {

        if visited[x][y] == '0' { return; } //방문한 노드일 경우 returm
        let c = visited[x][y];
        let next = &mut trie.node;
        if !next.contains_key(&c) { return; } //찾아야되는 character가 아닐 경우 종료

        //현재 Node
        let mut next_trie = next.get_mut(&c).unwrap();

        //찾고자하는 문자열에 도달했을 경우
        if next_trie.word != "".parse::<String>().unwrap() {
            answer.push(next_trie.word.parse().unwrap());
            next_trie.word = "".parse().unwrap(); //중복 탐색을 피하기 위해 None으로 변경
        }

        //현재 loop에서 방문 표시
        visited[x][y] = '0';

        //left check
        if x > 0 {
            Self::search_position(&mut visited, answer, next_trie, x - 1, y);
        }
        //rigth check
        if x < visited.len() - 1 {
            Self::search_position(&mut visited, answer, next_trie, x + 1, y);
        }
        //top check
        if y < visited[0].len() - 1 {
            Self::search_position(&mut visited, answer, next_trie, x, y + 1);
        }
        //bottom check
        if y > 0 {
            Self::search_position(&mut visited, answer, next_trie, x, y - 1);
        }

        //현재 loop 종료 다시 되돌려놓음
        visited[x][y] = c;
    }
}

Trie알고리즘을 사용한다.

words의 데이터로 Trie data structure를 만들어 둔다.

Trie는 HashMap으로 구성되어 있으며 가장 깊은 Depth에 완성된 word가 저장되어 있다. (words의 원소)

2차원 배열 board를 순회하며 DFS를 이용하여 상하좌우로 탐색 할 수 있도록 한다.

기존에 탐색한 cell은 '0'으로 바꾼 후 탐색하여 중복 탐색을 방지, 탐색을 마쳤다면 다시 되돌려 놓는다.

Trie의 가장 깊은 Depth까지 도달하게 될 경우 board에서 search 완료이다.

해당 word를 최종 반환 해야 되는 배열 answer vector에 push

Time Complexity => O(n * m)

Space Complexity => O(n * m)

//Trie
//words => pea, rain, oath, eat
Trie {
    next: {
        'p': Trie {
            next: {
                'e': Trie {
                    next: {
                        'a': Trie {
                            next: {},
                            word: "pea",
                        },
                    },
                    word: "",
                },
            },
            word: "",
        },
        'r': Trie {
            next: {
                'a': Trie {
                    next: {
                        'i': Trie {
                            next: {
                                'n': Trie {
                                    next: {},
                                    word: "rain",
                                },
                            },
                            word: "",
                        },
                    },
                    word: "",
                },
            },
            word: "",
        },
        'o': Trie {
            next: {
                'a': Trie {
                    next: {
                        't': Trie {
                            next: {
                                'h': Trie {
                                    next: {},
                                    word: "oath",
                                },
                            },
                            word: "",
                        },
                    },
                    word: "",
                },
            },
            word: "",
        },
        'e': Trie {
            next: {
                'a': Trie {
                    next: {
                        't': Trie {
                            next: {},
                            word: "eat",
                        },
                    },
                    word: "",
                },
            },
            word: "",
        },
    },
    word: "",
}