Leetcode 212.Word Search II

문제 링크

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

문제 해석

• m * n 인 board 배열
• string[] 인 words 배열
• words 에 해당하는 문자열이 board 에 존재하는지 확인
• 인접은 수평 과 수직 연결만 허용 ( 대각선 X )

문제 해결

• 모든 경우에 대해 Trie 를 넣자
  => 배열을 통해 , 방문한 곳 가는걸 방지
• Trie 를 순회하며 , 단어를 검색하자

슈도 코드

	function dfs(array,x,y,trie)

	if array.length >=10
		return
	if x== -1 or x== board.length
		return
	if y==-1 or y == board[x].length
		return
	if ([x,y] in array):
		return
	array.append([x,y])
	if trie [ board[x][y] ] == Null:
		trie[board[[x][y]] = {}
	trie = trie[board[x][y]]
	dfs(array,x,y+1,trie)
	dfs(array,x,y-1,trie)
	dfs(array,x+1,y,trie)
	dfs(array,x-1,y,trie) 

trie = root Trie
for (x : board 0~board.length)
	for (y: element 0~board[x].length)
		ary = []
		dfs(ary,x,y,trie)

---  그후 Trie 검색

결과

![[Pasted image 20230913183310.png]]

• 시간 초과
• 65개 중 63개 통과

사담

• 당연히 시간 초과나 메모리 초과가 뜰 거 같았는데 , 65개 중 63개의 준수한 통과
• Hard 문제는 Success 를 최대한 높이는데 의의를 둬야 할 거 같다.
• 다른 사람들 코드 보면 , 비슷한 거 같은데 간 곳인지 확인하는 dfs 적 부분에서

메모본

![[노드 - 0 15.jpg]]

Writed By Obisidan