[LeetCode] 212. Word Search II

 轉自LeetCode

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.

Solution

79. Word Search 的衍生題

可以用同一套解法，但要注意的是，words 可能會有重複的字串

所以可以用 set 先避免重複並加速計算

kotlin

	class Solution {
	val ans = mutableSetOf<String>()
	fun findWords(board: Array<CharArray>, words: Array<String>): List<String> {
	for(w in words) {
	for(r in board.indices) {
	for(c in board[0].indices) {
	if(!ans.contains(w) && dfs(0, r, c, board, w)) {
	ans.add(w)
	}
	}
	}
	}
	return ans.toList()
	}
	fun dfs(index: Int, row: Int, col: Int, board: Array<CharArray>, word: String): Boolean {
	when {
	index == word.length -> return true
	row < 0 -> return false
	col < 0 -> return false
	row > board.lastIndex -> return false
	col > board[0].lastIndex -> return false
	board[row][col] != word[index] -> return false
	}
	val tmp = board[row][col]
	board[row][col] = '*'
	val res = dfs(index+1, row-1, col, board, word)
	|| dfs(index+1, row+1, col, board, word)
	|| dfs(index+1, row, col-1, board, word)
	|| dfs(index+1, row, col+1, board, word)
	board[row][col] = tmp
	return res
	}
	}

view raw word_search_2.kt hosted with ❤ by GitHub