[알고리즘/python] LeetCode 212. Word Search II

📑 1. 문제 이해

https://leetcode.com/problems/word-search-ii/?envType=study-plan-v2&envId=top-interview-150 

Word Search II - LeetCode

☑️ 테스트케이스

문제에서 주어진 테스트 케이스를 분석해보면 다음과 같습니다. 

 

Example1: 

 

추가로 살펴봐야할 테스트 케이스는 다음과 같습니다.

 

 

💡 2. 알고리즘 설계

ㄴㅁㅇㄹㄴㅇㄹ

 

1. 순서1

2. 순서2

3. 순서3

4. 순서3

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        m = len(board)
        n = len(board[0])

        di = (0, 0, 1, -1)
        dj = (1, -1, 0, 0)

        EOW = "EOW"
        root = dict()
        for word in words:
            curr = root
            for c in word:
                if c not in curr:
                    curr[c] = dict()
                curr = curr[c]
            curr[EOW] = word

        # trie에서 eow에서 string 찾을 수 있는 방법?
        # # 에 eof를 저장한다.
        def dfs(i: int, j: int, visited: List[List[bool]], node: Dict[str, Dict]):
            visited[i][j] = True

            children = node[board[i][j]]
            # 이미 탐색한 word는 제거한다.
            if EOW in children:
                result.append(children[EOW])
                children.pop(EOW)

            for k in range(len(di)):
                ni = i + di[k]
                nj = j + dj[k]
                if not ((0 <= ni < m) and (0 <= nj < n)):
                    continue
                if visited[ni][nj]:
                    continue
                if board[ni][nj] not in children:
                    continue
                dfs(ni, nj, visited, children)

            visited[i][j] = False

            if not children:
                node.pop(board[i][j])

        visited = [[False] * n for _ in range(m)]
        result = []

        # visited를 사용하지 않아도 되는 이유
        for i in range(m):
            for j in range(n):
                if board[i][j] in root:
                    dfs(i, j, visited, root)
        return result

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N)

공간 복잡도: O(N)

 

⚒️ 3. 최적화

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N)

공간 복잡도: O(N)

 ⎌ 4. 검토

 

---

🤔 다른 사람의 풀이

 

코드

시간 복잡도 및 공간 복잡도

시간 복잡도: O(N)

공간 복잡도: O(N)

---

✅ 정리

◎ 정리1