dfs-单词匹配2

题目描述
在一个字符矩阵中，可把横向或竖向连续相邻的字符、按顺序组成一个单词，例如下图所示的 XE、ACX、STJIIE
给定一个字符矩阵 charMatrix 和目标单词列表 words，请计算这个字符矩阵可以组成多少个 words 中的单词，并返回这个数量：

矩阵中每个格子的字符，对于同一个单词不能重复使用；在不同的单词之间可以重复使用。
格子字符为 ? 表示通配符，可以匹配任一字母。
解答要求
时间限制：1000ms, 内存限制：256MB
输入
首行两个整数 rows 和 cols，1 <= rows, cols <= 5
随后 rows 行，每行有 cols 个字符，表示给定的字符矩阵，字符矩阵仅由大写字母或字符?组成
最后两行输入单词数量及单词列表 words，单词仅由大写字母组成，且单词不重复，1 <= words.length <= 100，1 <= words[i].length <= 8

输出
一个整数，表示字符矩阵可以组成 words 中的单词数量

样例
输入样例 1 复制

3 4
ACEI
EX?I
SSTJ
8
ACX II STJIIE XE NXE ACA ACECTJ ACETJ
输出样例 1

6
提示样例 1
ACX, II, STJIIE, XE 这四个单词可由矩阵中连续相邻格子的字符组成。
利用通配符后，单词 NXE 可由矩阵中 ?XE 组成； 同理 ACECTJ 也可组成。
但 ACA 和 ACETJ 无法组成。

输入样例 2 复制

5 5
A?JFL
J?ASD
DG?OI
G??GB
A?OFC
7
A AA AAA AAAAAAAA ADJAS ADJAJDA LDSFL
输出样例 2

6
提示样例 2
只有 LDSFL 无法组成

算法实现思路：
实现思路如下： 
 
1. 遍历单词列表中的每个单词。 
2. 对于每个单词，使用 matchWord 函数在字符矩阵中查找匹配的单词。 
3.  matchWord 函数遍历字符矩阵中的每个位置，如果当前位置的字符与单词的第一个字符相等或者为通配符 "?"，则调用 dfs 函数进行深度优先搜索。 
4.  dfs 函数递归地探索字符矩阵中的上、下、左、右四个方向，查找与单词剩余部分匹配的字符。 
5. 如果找到匹配的单词，则返回 true ，否则返回 false 。 
6. 在 getNumWords 函数中，如果找到匹配的单词，则将计数器加一。 
7. 最后返回计数器的值。 
 

代码如下：
 
package main

import (
	"fmt"
)

// 待实现函数，在此函数中填入答题代码
func getNumWords(charMatrix []string, words []string) int {
	ans := 0
	maxX := len(charMatrix)
	maxY := len(charMatrix[0])
	visited := make([][]bool, maxX)
	for i := 0; i < maxX; i++ {
		visited[i] = make([]bool, maxY)
	}
	for _, word := range words {
		if matchWord(word, charMatrix, maxX, maxY, visited) {
			ans++
		}
	}
	return ans
}

func matchWord(word string, charMatrix []string, maxX, maxY int, visited [][]bool) bool {
	for x := 0; x < maxX; x++ {
		for y := 0; y < maxY; y++ {
			if charMatrix[x][y] == word[0] || charMatrix[x][y] == '?' {
				if dfs(word, x, y, charMatrix, maxX, maxY, visited) {
					return true
				}
			}
		}
	}
	return false
}

func dfs(word string, x int, y int, charMatrix []string, maxX, maxY int, visited [][]bool) bool {
	if x < 0 || x >= maxX || y < 0 || y >= maxY || visited[x][y] {
		return false
	}
	w := charMatrix[x][y]
	if w == word[0] || w == '?' {
		if len(word) == 1 {
			return true
		}
		visited[x][y] = true
		substring := word[1:]
		result := dfs(substring, x+1, y, charMatrix, maxX, maxY, visited) || dfs(substring, x-1, y, charMatrix, maxX, maxY, visited) || dfs(
			substring, x, y+1, charMatrix, maxX, maxY, visited) || dfs(substring, x, y-1, charMatrix, maxX, maxY, visited)
		visited[x][y] = false
		return result
	}
	return false
}

func main() {
	fmt.Println(getNumWords([]string{
		"ACEI",
		"EX?I",
		"SSTJ",
	}, []string{
		"ACX",
		"II",
		"STJIIE",
		"XE",
		"NXE",
		"ACA",
		"ACECTJ",
		"ACETJ",
	}))
}