2022-01-23：力扣425，单词方块。
给定一个单词集合 （没有重复），找出其中所有的 单词方块 。
一个单词序列形成了一个有效的单词方块的意思是指从第 k 行和第 k 列 (0 ≤ k < max(行数, 列数)) 来看都是相同的字符串。
例如，单词序列 [“ball”,“area”,“lead”,“lady”] 形成了一个单词方块，因为每个单词从水平方向看和从竖直方向看都是相同的。
注意：
单词个数大于等于 1 且不超过 500。
所有的单词长度都相同。
单词长度大于等于 1 且不超过 5。
每个单词只包含小写英文字母 a-z。
答案2022-01-23：
递归。所有单词的所有前缀都会成为key。
注意！课上介绍题目设定的时候，有一点点小错
题目描述如下：
给定n个字符串，并且每个字符串长度一定是n，请组成单词方阵，比如：
给定4个字符串，长度都是4，[“ball”,“area”,“lead”,“lady”]
可以组成如下的方阵：
b a l l
a r e a
l e a d
l a d y
什么叫单词方阵？如上的方阵可以看到，
第1行和第1列都是"ball"，第2行和第2列都是"area"，第3行和第3列都是"lead"，第4行和第4列都是"lady"
所以如果有N个单词，单词方阵是指:
一个NN的二维矩阵，并且i行和i列都是某个单词，不要求全部N个单词都在这个方阵里。
请返回所有可能的单词方阵。
示例：
输入: words = [“abat”,“baba”,“atan”,“atal”]
输出: [[“baba”,“abat”,“baba”,“atal”],[“baba”,“abat”,“baba”,“atan”]]
解释：
可以看到输出里，有两个链表，代表两个单词方阵
第一个如下：
b a b a
a b a t
b a b a
a t a l
这个方阵里没有atan，因为不要求全部单词都在方阵里
第二个如下：
b a b a
a b a t
b a b a
a t a n
这个方阵里没有atal，因为不要求全部单词都在方阵里
课上说的是：一个NN的二维矩阵，并且i行和i列都是某个单词，要求全部N个单词都在这个方阵里
原题说的是：一个N*N的二维矩阵，并且i行和i列都是某个单词，不要求全部N个单词都在这个方阵里
讲的过程没错，但是介绍题意的时候，这里失误了
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
ret := wordSquares([]string{"abat", "baba", "atan", "atal"})
fmt.Println(ret)
}
func wordSquares(words []string) [][]string {
n := len(words[0])
// 所有单词，所有前缀字符串，都会成为key！
map0 := make(map[string][]string)
for _, word := range words {
for end := 0; end <= n; end++ {
prefix := word[0:end]
map0[prefix] = append(map0[prefix], word)
}
}
ans := make([][]string, 0)
process(0, n, map0, &([]string{}), &ans)
return ans
}
// i, 当前填到第i号单词，从0开始，填到n-1
// map, 前缀所拥有的单词
// path, 之前填过的单词, 0...i-1填过的
// ans, 收集答案
func process(i, n int, map0 map[string][]string, path0 *[]string, ans *[][]string) {
if i == n {
pathc := make([]string, len(*path0))
copy(pathc, *path0)
*ans = append(*ans, pathc)
} else {
// 把限制求出来，前缀的限制！
builder := make([]byte, 0)
for _, pre := range *path0 {
builder = append(builder, pre[i])
}
prefix := string(builder)
if _, ok := map0[prefix]; ok {
for _, next := range map0[prefix] {
*path0 = append(*path0, next)
process(i+1, n, map0, path0, ans)
*path0 = (*path0)[0 : len(*path0)-1]
}
}
}
}
执行结果如下：
左神java代码
