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代码