LeetCode 솔루션

[11/5] 212. Word Search II

학부유학생 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.11.05 10:46

9,882 조회
1 댓글
0 추천
0 비추천
목록 게시글 쓰기

Hard

7661347Add to ListShare

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.

Example 1:

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

Example 2:

Input: board = [["a","b"],["c","d"]], words = ["abcb"]
Output: []

Constraints:

m == board.length
n == board[i].length
1 <= m, n <= 12
board[i][j] is a lowercase English letter.
1 <= words.length <= 3 * 104
1 <= words[i].length <= 10
words[i] consists of lowercase English letters.
All the strings of words are unique.

Accepted

512,675

Submissions

1,388,063

#Amazon, #Uber, #Cisco, #Microsoft, #Bloomberg, #Apple, #Karat, #Facebook, #Google, #Indeed, #TikTok

링크

https://leetcode.com/problems/word-search-ii/ 2939 회 연결

익명
작성일 2022.11.05 10:46

class TrieNode:
    def __init__(self):
        self.word = None
        self.children = {}
        
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        trieroot = TrieNode()
        
        for word in words:
            node = trieroot
            
            for idx, char in enumerate(word):
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
                if idx == len(word)-1:
                    node.word = word
        
        directions = [(1,0), (0,1), (-1,0), (0,-1)]
        
        ROW, COL = len(board), len(board[0])
        path = set()
        
        res = []
        
        def dfs(row, col, trienode):
            if trienode.word:
                res.append(trienode.word)
                trienode.word = None
            path.add((row,col))
            
            for rd, cd in directions:
                nr, nc = row+rd, col+cd
                if 0<=nr<ROW and 0<=nc<COL and (nr,nc) not in path and board[nr][nc] in trienode.children:
                    dfs(nr,nc,trienode.children[board[nr][nc]])
            
            path.remove((row,col))
        
        for r in range(ROW):
            for c in range(COL):
                if board[r][c] in trieroot.children:
                    node = trieroot
                    dfs(r,c,node.children[board[r][c]])
        return res

[code=Python 3]class TrieNode:
    def __init__(self):
        self.word = None
        self.children = {}
        
class Solution:
    def findWords(self, board: List[List[str]], words: List[str]) -> List[str]:
        trieroot = TrieNode()
        
        for word in words:
            node = trieroot
            
            for idx, char in enumerate(word):
                if char not in node.children:
                    node.children[char] = TrieNode()
                node = node.children[char]
                if idx == len(word)-1:
                    node.word = word
        
        directions = [(1,0), (0,1), (-1,0), (0,-1)]
        
        ROW, COL = len(board), len(board[0])
        path = set()
        
        res = []
        
        def dfs(row, col, trienode):
            if trienode.word:
                res.append(trienode.word)
                trienode.word = None
            path.add((row,col))
            
            for rd, cd in directions:
                nr, nc = row+rd, col+cd
                if 0<=nr<ROW and 0<=nc<COL and (nr,nc) not in path and board[nr][nc] in trienode.children:
                    dfs(nr,nc,trienode.children[board[nr][nc]])
            
            path.remove((row,col))
        
        for r in range(ROW):
            for c in range(COL):
                if board[r][c] in trieroot.children:
                    node = trieroot
                    dfs(r,c,node.children[board[r][c]])
        return res[/code]