<Hard> Word Search II (LeetCode : C#)

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

📕 문제 설명

mxn 사이즈의 문자로 구성된 board와 단어 배열이 주어질 때 board에서 만들 수 있는 모든 단어들 반환하기

단어는 인접한 칸들을 순차적으로 연결해서 만든다. (가로, 세로 인접) 추가로 단어에는 중복되는 문자를 넣지 않는다.

• Input
  board 정보, 단어 배열
• Output
  만들 수 있는 모든 단어

예제

시도 1.

완전 탐색 (시간 초과)

public class Solution {
    int[] dirX = new int[4] {1, 0, -1, 0};
    int[] dirY = new int[4] {0, 1, 0, -1};
    HashSet<string> possibleWords;
    HashSet<string> answer;
    int maxLengthOfWord;
    int maxXLength;
    int maxYLength;
    char[][] boardInfo;
    public IList<string> FindWords(char[][] board, string[] words) {
        answer = new HashSet<string>();
        possibleWords = new HashSet<string>();
        maxLengthOfWord = 0;
        maxXLength = board.Length;
        maxYLength = board[0].Length;
        boardInfo = board;

        foreach(string word in words) // 단어 hashset에 담아서 확인 위함
        {
            possibleWords.Add(word);
            maxLengthOfWord = maxLengthOfWord >= word.Length ? maxLengthOfWord : word.Length;
        }

        HashSet<char> currentVisitdChar = new HashSet<char>();
        bool[,] visited = new bool[maxXLength, maxYLength];
        for (int i = 0; i < maxXLength; i++)
        {
            for (int j = 0; j < maxYLength; j++)
            {
                FindWord(i, j, visited, "");
            }
        }
        return answer.ToList();
    }

    public void FindWord(int posX, int posY, bool[,] visited, string currentWord)
    {
        bool[,] currentVisited = (bool[,]) visited.Clone();
        currentWord += boardInfo[posX][posY];
        currentVisited[posX, posY] = true;
        if (currentWord.Length > maxLengthOfWord) return; // 최대 길이보다 길면 볼 필요 없으므로 패스
        if (possibleWords.Contains(currentWord)) answer.Add(currentWord); // 단어 정답에 포함 가능하면 추가하기

        for (int i = 0; i < 4; i++)
        {
            int newX = posX + dirX[i];
            int newY = posY + dirY[i];
            if (newX < 0 || newX >= maxXLength || newY < 0 || newY >= maxYLength) continue;
            if (currentVisited[newX, newY]) continue; // 현재 방문한 위치면 패스
            FindWord(newX, newY, currentVisited, currentWord);
        }
    }
}

시도 2.

위 코드에서 최대 길이인 단어 봤으면 그 다음 최대길이로 갱신해주는 식으로 해서 불필요한 개수만큼 보는걸 줄이도록 변경했다.

public class Solution {
    int[] dirX = new int[4] {1, 0, -1, 0};
    int[] dirY = new int[4] {0, 1, 0, -1};
    HashSet<string> possibleWords;
    HashSet<string> answer;
    List<int> maxLengths;
    int maxXLength;
    int maxYLength;
    char[][] boardInfo;
    int currMaxLengthIndex;
    public IList<string> FindWords(char[][] board, string[] words) {
        answer = new HashSet<string>();
        possibleWords = new HashSet<string>();
        maxLengths = new List<int>();
        maxXLength = board.Length;
        maxYLength = board[0].Length;
        boardInfo = board;
        currMaxLengthIndex = 0;

        foreach(string word in words) // 단어 hashset에 담아서 확인 위함
        {
            possibleWords.Add(word);
            maxLengths.Add(word.Length);
        }

        maxLengths.Sort();
        maxLengths.Reverse();

        HashSet<char> currentVisitdChar = new HashSet<char>();
        bool[,] visited = new bool[maxXLength, maxYLength];
        for (int i = 0; i < maxXLength; i++)
        {
            for (int j = 0; j < maxYLength; j++)
            {
                FindWord(i, j, visited, "");
            }
        }
        return answer.ToList();
    }

    public void FindWord(int posX, int posY, bool[,] visited, string currentWord)
    {
        if (currMaxLengthIndex >= maxLengths.Count) return;
        bool[,] currentVisited = (bool[,]) visited.Clone();
        currentWord += boardInfo[posX][posY];
        currentVisited[posX, posY] = true;
        if (currentWord.Length > maxLengths[currMaxLengthIndex]) return; // 최대 길이보다 길면 볼 필요 없으므로 패스
        if (possibleWords.Contains(currentWord)) 
        {
            if (!answer.Contains(currentWord))
            {
                answer.Add(currentWord); // 단어 정답에 포함 가능하면 추가하기
                if (currentWord.Length == maxLengths[currMaxLengthIndex])
                {
                    currMaxLengthIndex++;
                }
            }

        }

        for (int i = 0; i < 4; i++)
        {
            int newX = posX + dirX[i];
            int newY = posY + dirY[i];
            if (newX < 0 || newX >= maxXLength || newY < 0 || newY >= maxYLength) continue;
            if (currentVisited[newX, newY]) continue; // 현재 방문한 위치면 패스
            FindWord(newX, newY, currentVisited, currentWord);
        }
    }
}

(마지막 테케는 너무 길어서 안나오는건가..?)

풀이

Trie 구조 사용해서 풀었다.
1) 단어를 돌면서 단어들을 trie 구조에 나타낸다.
if문에서는 root 기준 새로운 문자가 들어올때 해당 값을 기반으로 트리를 만들어 나가게 된다. (그림에서는 o, p, e, r에 해당됨)
그 다음 node의 children들을 가리키도록 해서 그 다음 문자에 대해 또 반복 반복 하는 식으로 한다. 최종적으로 아래의 그림과 같이 만들어진다.

        // 각 단어를 trie로 나타내기 
        TrieNode root = new TrieNode();
        foreach (string word in words) 
        {
            TrieNode node = root;
            foreach (char c in word) 
            {
                if (node.Children[c - 'a'] is null) node.Children[c - 'a'] = new TrieNode();
                node = node.Children[c - 'a'];
            }
            node.Word = word;
        }

2) 각 board의 문자들을 기준으로 dfs 돌려서 단어들 추가한다.

public class Solution {
    public IList<string> FindWords(char[][] board, string[] words) {
        int m = board.Length;
        int n = board[0].Length;
        List<string> answer = new List<string>();
        
        // 각 단어를 trie로 나타내기 
        TrieNode root = new TrieNode();
        foreach (string word in words) 
        {
            TrieNode node = root;
            foreach (char c in word) 
            {
                if (node.Children[c - 'a'] is null) node.Children[c - 'a'] = new TrieNode();
                node = node.Children[c - 'a'];
            }
            node.Word = word;
        }
        
        for (int i = 0; i < m; i++) 
        {
            for (int j = 0; j < n; j++) 
            {
                Dfs(i, j, root);
            }
        }
        
        return answer;
        
        void Dfs(int i, int j, TrieNode node) 
        {
            if (i < 0 || j < 0 || i == m || j == n) return; // board 범위 밖
            char c = board[i][j]; // 현재 board 문자
            if (c == '0' || node.Children[c - 'a'] is null) return; // trie 연걸에 해당되는거 없는 경우
            node = node.Children[c - 'a'];
            
            if (node.Word is not null) // 있는 단어는 추가하고 trie에서 빼기
            {
                answer.Add(node.Word);
                node.Word = null;
            }
            
            board[i][j] = '0'; // visited 처리
            Dfs(i - 1, j, node);
            Dfs(i, j - 1, node);
            Dfs(i + 1, j, node);
            Dfs(i, j + 1, node);
            board[i][j] = c;
        }
    }
}

public class TrieNode 
{
    public TrieNode[] Children = new TrieNode[26];
    public string Word;
}

결과