[LeetCode题解]79. 单词搜索

题目描述

[LeetCode题解]79. 单词搜索

题目:79. 单词搜索

解题思路

遍历

首先找重复性,题目说给定单词是否存在于二维数组中,可以简化为从 (x, y) 走 n 步(n 表示单词长度),查看给定单词是否存在。然后再遍历二维数组里的所有点,看是否存在给定单词。

func exist(board [][]byte, word string) bool {
    for x:=0;x<n;x++ {
        for y:=0;y<m;y++ {
            if dfs(x, y, 0) {
                return true
            }
        }
    }
    return false
}

回溯

从 (x, y) 走 n 步,每一步都可以从上下左右四个方向“试探步”,直到走完 n 步,然后再比较“走过的路径” 和给定单词是否相等。

func backtrack(x int, y int, index int, s *[]byte) {
    // 终止条件:走完 n 步
    if index == len(word) { 
        return string(s) == word
    }
    if !visited[x][y] {
        visited[x][y] = true
        s = append(s, board[x][y])
        
        for i:=0;i<direction;i++ {
            newX, newY := x+direction[i][0], y+direction[i][1]
            if backtrack(newX, newY, index+1) {
                return true
            }
        }
        
        s = s[:len(s)]
        visited[x][y] = false
    }
    return false
}

此代码存在问题,没有考虑边界的问题,当向上下左右移动时,不能超过边界,因此代码调整为:

func backtrack(x int, y int, index int, s *[]byte) {
    // 终止条件:走完 n 步
    if index == len(word) { 
        return string(s) == word
    }
    if !visited[x][y] {
        visited[x][y] = true
        s = append(s, board[x][y])
        
        for i:=0;i<direction;i++ {
            newX, newY := x+direction[i][0], y+direction[i][1]
            if inArea(newX, newY) && backtrack(newX, newY, index+1) {
                return true
            }
        }
        
        s = s[:len(s)]
        visited[x][y] = false
    }
    return false
}

func inArea(x int, y int) bool {
	return x < n && x >= 0 && y < m && y >= 0
}

剪枝

上面的代码可以进一步优化,在回溯过程中,可以预先判断结果,假如走到第 i 步时,此时的字符与给定单词的第 i 位字符不相等,则可以剪掉后续的比较,即剪掉分支。

注:回溯、dfs 本质上是递归,函数调用的过程会生成一颗递归树。

func backtrack(x int, y int, index int) bool {
	if index == len(word)-1 {
		return board[x][y] == word[index]
	}

	if board[x][y] == word[index] {
		visited[x][y] = true
		// 遍历四个方向
		for i := 0; i < len(direction); i++ {
			newX, newY := x+direction[i][0], y+direction[i][1]
			if inArea(newX, newY) && !visited[newX][newY] {
				if backtrack(newX, newY, index+1) {
					return true
				}
			}
		}
		visited[x][y] = false
	}

	return false
}

func inArea(x int, y int) bool {
	return x < n && x >= 0 && y < m && y >= 0
}

代码实现

var direction = [][]int{{1, 0}, {-1, 0}, {0, 1}, {0, -1}}
var visited [][]bool
var n, m int

func exist(board [][]byte, word string) bool {
	n = len(board)
	if n == 0 {
		return false
	}
	m = len(board[0])
	if m == 0 {
		return false
	}
	visited = make([][]bool, n)
	for i := 0; i < n; i++ {
		visited[i] = make([]bool, m)
	}

	for x := 0; x < n; x++ {
		for y := 0; y < m; y++ {
			if backtrack(board, word, 0, x, y) {
				return true
			}
		}
	}
	return false
}

func backtrack(board [][]byte, word string, index int, x int, y int) bool {
	if index == len(word)-1 {
		return board[x][y] == word[index]
	}

	if board[x][y] == word[index] {
		visited[x][y] = true
		// 遍历四个方向
		for i := 0; i < len(direction); i++ {
			newX, newY := x+direction[i][0], y+direction[i][1]
			if inArea(newX, newY) && !visited[newX][newY] {
				if backtrack(board, word, index+1, newX, newY) {
					return true
				}
			}
		}
		visited[x][y] = false
	}

	return false
}

func inArea(x int, y int) bool {
	return x < n && x >= 0 && y < m && y >= 0
}

复杂度分析:

  • 时间复杂度:O(n * m * L),其中 n, m, L 分别表示二维数组的行、列和给定单词的长度。
    • 最好情况,遍历二维数组第一个元素,且走一次就找到。
    • 最坏情况,要遍历到二维数组的最后一个元素,并且各个方向都走完后,没找到结果。
  • 空间复杂度:O(n * m),其中 n, m 分别表示二维数组的行、列。只需要一个二维数组记录是否访问过元素。

总结

  • 对于类似排列、组合的问题,第一时间要想到可以使用dfs、回溯来解决。
  • 一般来说,回溯和剪枝是一起使用的,在优化时间复杂度时,记得考虑剪枝。
上一篇:矩阵中的路径


下一篇:[LeetCode] 489. Robot Room Cleaner