LeetCode 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.

 

 

 

풀이

알파벳으로  이루어진 2차원 리스트가 주어지고  단어의 배열이 주어진다,

 

배열안에 존재하는 단어를 리스트에 담아서 제출하면 된다.

 

방법

트라이트리(trietree) 자료구조를 활용해서 단어를 넣은 트라이트리를 만들고 매트리스마다 y,x축으로 나누어 dfs로 2차원리스트를 탐색해 어떤 단어들이 존재하는지 찾는다. 

 

class Node:
    def __init__(self):
        self.children={}
        self.endof =0

class Trie(object):
    def __init__(self):
        self.root = Node()
    def insert(self, word): # 노드 삽입, 딕셔너리로 존재하지않는다면 생성, 존재한다면 추가 
        node = self.root
        for i in word:
            if i not in node.children:
                node.children[i] = Node()
            node= node.children[i] 
        node.endof =1   # 완성문자열



class Solution(object):
    def findWords(self, board, words):
        self.result = []
        trie = Trie() # trieTree 생성
        node = trie.root
        for i in words: # 트라이트리에 단어 삽입
            trie.insert(i)
        for y in range(len(board)):
            for x in range(len(board[0])):
                self.search(node,board,y,x,"")
    def search(self,node,board,y,x,temp):
        dy,dx = [0,0,1,-1],[1,-1,0,0]
        if node.endof: # 현재 완성된 단어라면 tmep result에 추가 
            self.result.append(temp)
            node.endof = 0 #방문체크 
            if not node: 
                return
        if 0>y>=len(board) or 0>x>=len(board[0]): #범위체크
            return
        char = board[y][x] # 현재 위치의 문자열 확인
        if char not in node.children: # 현재 노드의 해시맵에 없다면 리턴
            return
        node = node.children[char] #node 현재 char의 인덱스로 변경
        for i in range(4): # ny,nx재지정 상하좌우
            ny,nx = y+dy[i],x+dx[i]
            self.search(node,board,ny,nx,temp+char) # 재귀적으로 탐색

 

오류나서 생긴 문제

 

1.board의 방문리스트를 사용하지 않아서 최초에 오류가 났었는데 ( 왔던 경로 재방문) , 이걸 위해 board를 '*'문자열로 바꿨다가 findword의 2차원탐색에서 다른 위치에서 시작할 때 오류 발생,  변경된 문자열로 새로 찾을 수 없음

   -> search의 for문으로 ny,nx 변경시에만 값 변경

 

2.시간초과

모든 경로를 2차원리스트에서 dfs로 모두 찾으려하니 시간이 초과됨