212. Word Search II

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.

My Answer 1: Accepted (Runtime: 44 ms - 70.35% / Memory Usage: 14.1 MB - 97.70%)

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        ## RC ##
        ## RECURSIVE ##
        ## similar to Number of Islands ##
        def search(board, i, j, word):
            
            if(len(word) == 0):
                return True
            
            if(i < 0  or i >= len(board) or j < 0 or j >= len(board[0]) or board[i][j] != word[0]):
                return False
            
            temp = board[i][j]
            board[i][j] = '$'
            
            result = search(board, i+1, j, word[1:]) or search(board, i-1, j, word[1:]) or search(board, i, j+1, word[1:]) or search(board, i, j-1, word[1:])
            
            board[i][j] = temp
            return result
        
        res = []
        for word in words:
            for i in range(len(board)):
                for j in range(len(board[0])):
                    if search(board, i, j, word):           
                        res.append(word)
                        break
                        
        res = list(set(res))
        
        return res

전에 풀었던 79. Word Search 코드를 살짝 수정했음

words 의 word 를 하나씩 search 해주고 마지막에 res = list(set(res)) 로 중복 제거

하지만 3 중 for 문이라는 점...^^

Trie with DFS

Solution 1: Runtime: 9816 ms -5.00% / Memory Usage: 14.4 MB - 46.27%

class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        ## RC ##
		## APPROACH : TRIE + DFS ##
		## LOGIC ##
		#	1. build trie with all words list
		#	2. start scanning matrix, move in all four directions and check if such combination exists in the trie
		#	3. make sure you donot return when result is found ( case: words = [cat, cattle ] )
		
        ## TIME COMPLEXICITY : O(M(4x3^(L-1))) ## (M is the number of cells in the board and L is the maximum length of words.)
		## SPACE COMPLEXICITY : O(N) ##
	    
        def dfs(i, j, curr, currNode):
            ch = board[i][j]
            if( ch not in currNode.children or (i, j) in visited ):
                return
            if currNode.children[ch].endOfWord:
                res.add(curr)
                # return                            # edge case
            visited.add((i,j))
            for x,y in directions:
                if 0 <= i + x < m and 0 <= j + y < n:
                    dfs( i + x, j + y, curr + board[i + x][j + y], currNode.children[ch])
            visited.remove((i,j))   # edge case
        
        # buid trie data structure
        my_trie = Trie()
        [ my_trie.insert(word) for word in words ]
        rootNode = my_trie.get_rootNode()
        
        m, n = len(board), len(board[0])
        directions = [(0,1), (1,0), (0,-1), (-1,0)]
        res = set()                     
        for i in range(len(board)):
            for j in range(len(board[i])):
                visited = set()
                dfs(i, j, board[i][j], rootNode)
        return res
    
class TrieNode:
    def __init__(self):
        self.children = {}
        self.endOfWord = False

class Trie:
    def __init__(self):
        self.rootNode = TrieNode()
    
    def get_rootNode(self):
        return self.rootNode
    
    # Inserts a word into the trie.
    def insert(self, word: str) -> None:
        currNode = self.rootNode
        for idx, ch in enumerate(word):
            if( ch not in currNode.children ):
                currNode.children[ch] = TrieNode()
            currNode = currNode.children[ch]        
        currNode.endOfWord = True

런타임은 그지지만.. Trie 이짜씩을 쓰는게 맞나보다...

Trie 를 만들어서 words 속 word 들을 trie 에 모두 insert 해주고
res 는 중복이 없는 set 로 만들어서 dfs 해줌
visited 도 만들어서 방문했던 곳은 건너뛰도록 해줌

dfs)
1. 문자가 currNode.children 에 없거나 이미 방문했던 곳이면 그냥 return
2. 문자가 있고 마지막 문자면 찾은 거니까 res 에 넣어줌
3. 그 외에는 다음 문자를 찾아야 하므로 for x,y in directions: 에서 사방에 찾을 문자가 있는지 확인
=> dfs 재귀 돌림
4. 마지막에 visited.remove((i,j)) 는 다른 word 도 찾아야 하므로 해준 듯