Leetcode 212. WordSearch 2

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

Word Search II - LeetCode

 

board라는 매트릭스에서 words에서 찾을 수 있는 단어 리스트를 반환하는 문제입니다.

 

 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"]

 

---

 

matrix 문제 + 단어연결과 관련된 문제 ==> DFS + Trie의 조합으로 풀이를 해야하는 문제입니다.

저는 처음에 DFS 만으로 풀이를 해보겠다는 생각을 가지고 코드를 짰었는데요,,,, 역시나 TLE와 오류를 만나며 Trie 풀이를 분석해봤습니다 ㅎㅎㅎ

 

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        m, n = len(board), len(board[0])
        visit = [[False]*n for i in range(m)]
        
        def dfs(wrd,r,c):
            if len(wrd) == 0:
                return True
            visit[r][c] = True
            steps = [0,1,0,-1,0]
            for s in range(len(steps)-1):
                new_r = steps[s] + r
                new_c = steps[s+1] + c
                if 0<= new_r <m and 0<=new_c<n and not visit[new_r][new_c] and board[new_r][new_c] == wrd[0]:
                    if dfs(wrd[1:],new_r,new_c):
                        visit[new_r][new_c] =False
                        return True
            visit[new_r][new_c] = False
            return False
       
        res = []
        for word in words:
            wasfound = False
            for i in range(m):
                for j in range(n):
                    if board[i][j] == word[0]:
                        if dfs(word[1:],i,j) and word not in res:
                            res.append(word)
                            wasfound = True
                            break
                if wasfound:
                    break

        return res

 

---

728x90

 

이 문제는 여러 알고리즘 개념이 접합된 것도 좋았지만,

창의적으로 Trie를 만든 코드들을 보면서 많이 배울 수 있었던 문제였습니다.

 

심플한 Trie 구조 활용)

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        m, n = len(board), len(board[0])
        res = []
        
        #Trie를 별도 클래스 없이 단 2 줄로 정의한 코드입니다
        Trie = lambda : defaultdict(Trie)
        root = Trie()
        
        def build_Trie(s):
            node = root
            for i in s:
                node = node[i]
            node['$'] = s
            
        for w in words:
            build_Trie(w)
            
        def dfs(i,j,root):
            loc = board[i][j]
            cur = root.get(loc)         #Trie에서 단어를 찾을 수 없으면 None을 반환하도록 get을 사용함
            if not cur:
                return
            if '$' in cur:              
                res.append(cur['$'])
                del cur['$']
                
            board[i][j] = '#'
            if i < m-1:
                dfs(i+1,j,cur)
            if i>0 :
                dfs(i-1,j,cur)
            if j < n-1:
                dfs(i,j+1,cur)
            if j>0:
                dfs(i,j-1,cur)
            board[i][j] = loc
            
        for i in range(m):
            for j in range(n):
                dfs(i,j,root)
        return res

 

 

🙌 lambda : defaultdict(Trie)

처음에 이 표현을 보고 어리둥절 했었는데요 스택오버플로우에서 답을 찾을 수 있었습니다.

 

아래 표현은 그 아래 표현과 동일한데요

Trie = lambda: collections.defaultdict(Trie)

def Trie():
    return collections.defaultdict(Trie)

 

defaultdict(list)나 defaultdict(int)를 하면 비어있는 value에 비어있는 리스트나 0이 할당되는 것처럼 Trie에 할당되는 값이 없을 때, Trie()가 할당됨을 의미합니다.

 

이전에 제가 풀었던 문제에서는 주로 이렇게 TrieNode와 Trie를 별도로 정의하고 Trie를 만들어나가는

구조를 가졌었는데요, 이번에 발견한 풀이에서는 코드를 짧으면서 간결하게 풀이했더라구요

 

class TrieNode:
	def __init__(self):
          self.children= {}
          self.isleaf = False
        
class Trie:
     def __init__(self):
        self.root = TrieNode()
    
     def insert(self,word):
         node = self.root
        
         for c in word:
             if c not in node.children:
                 node.children[c] = TrieNode()
             node= node.children[c]
         node.is_leaf = True

 

Leetcode에 은근히 Trie 관련 문제가 많은 것 같습니다. 열심히 풀면서 Trie는 눈감고 풀 때까지 달려봅시다~~

 

 

Reference:

https://stackoverflow.com/questions/51286423/using-lambda-and-defaultdict