题目描述
在一个字符矩阵中，可把横向或竖向连续相邻的字符、按顺序组成一个单词，例如下图所示的 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",
}))
}