题目描述
单词接龙，给定N个字符串s1,s2…..sN，（N<=20, len(s)<=20），从中选取若干个进行接龙，规则如下：
接龙时，后一单词的首字母必须与前一个单词的尾字母相同。
每个单词只能使用一次。
起始单词可任选。
在所有可能的接龙路径中，找到最长的单词串。若存在多个最长串，输出其中任意一个方案。
测试用例 1
输入
5
dog cat elephant rat tiger
输出
elephant-tiger-rat
用例分析
输入 [dog, cat, elephant, rat, tiger] 的最优解为 elephant-tiger-rat，其连接逻辑为：
elephant（尾 t）→ tiger（首 t）
tiger（尾 r）→ rat（首 r）
算法思路
由于单词数量限制为 N≤20，直接暴力搜索的时间复杂度为 O(N!)，显然不可行。此时可以采用 状态压缩动态规划（状压DP） 来高效解决。
状态压缩DP核心思想
状态表示
使用二进制数表示单词的使用状态。例如，i=1010（二进制）表示第2和第4个单词已被使用。
定义 dp[i][j]：状态为 i 且最后一个单词是第 j 个单词时，接龙的最大长度。
属性为 max，记录最大长度。
状态转移
遍历所有可能的转移：若当前状态为 i，最后一个单词为 j，则尝试所有未被使用的单词 k（即 i 的第 k 位为0）。
若 k 的首字母等于 j 的尾字母，则更新状态 i | (1 << k) 的值为 dp[i][j]+len(k)。
路径回溯
记录每个状态的前驱节点（即上一个单词），最终从最大长度的状态回溯路径。
预处理关键点
连接关系矩阵：预处理所有单词对的连接可能性（即 word[j] 的尾字母是否等于 word[k] 的首字母）。
二进制操作：利用位运算高效判断单词是否被使用 i&(1<<k)（例如 判断第 k 个单词是否被使用）。
代码实现
package main
import (
"fmt"
"slices"
)
func main() {
// 定义一个字符串切片，包含多个单词
words := []string{"word", "dd", "da", "dc", "dword", "d"}
// 调用 WordSolitaire 函数解决单词接龙问题，并将结果存储在 res 中
res := WordSolitaire(words)
// 打印最终的最长接龙序列
fmt.Println(res)
}
// WordSolitaire 函数用于解决单词接龙问题，找出给定单词列表中能形成的最长接龙序列
func WordSolitaire(words []string) []string {
// n 为单词列表的长度，stateMax 表示所有可能的状态数量，使用位运算 1 << len(words) 得到
n, stateMax := len(words), 1<<len(words)
// dp 数组用于记录以每个单词结尾，在每种状态下的最长接龙序列长度
dp := make([][]int, n)
// pre 数组用于记录在每种状态下，当前单词的前一个单词的索引，用于回溯路径
pre := make([][]int, n)
// 初始化 dp 和 pre 数组
for i := range dp {
dp[i] = make([]int, stateMax)
pre[i] = make([]int, stateMax)
}
// back 函数用于获取字符串的最后一个字符的 ASCII 码值
back := func(s string) int { return int(s[len(s)-1]) }
// front 函数用于获取字符串的第一个字符的 ASCII 码值
front := func(s string) int { return int(s[0]) }
// index 用于记录最长接龙序列的最后一个单词的索引
// state 用于记录最长接龙序列对应的状态
// size 用于记录最长接龙序列的长度
var index, state, size int
// 初始化每个单词单独作为一个接龙序列的情况
for i, word := range words {
// 状态 1 << i 表示只有第 i 个单词被使用
dp[i][1<<i] = len(word)
// 如果当前接龙序列长度大于之前记录的最长长度
if size < dp[i][1<<i] {
// 更新最长长度
size = dp[i][1<<i]
// 更新最长接龙序列的最后一个单词的索引
index = i
// 更新最长接龙序列对应的状态
state = 1 << i
}
}
// 遍历所有可能的状态
for k := 0; k < stateMax; k++ {
// 遍历每个单词
for i := range words {
// 如果当前状态下第 i 个单词未被使用，则跳过
if k&(1<<i) == 0 {
continue
}
// 再次遍历每个单词
for j := range words {
// 如果当前状态下第 j 个单词已经被使用，或者第 i 个单词的最后一个字符和第 j 个单词的第一个字符不相同，则跳过
if k&(1<<j) != 0 || back(words[i]) != front(words[j]) {
continue
}
// 计算新的状态，将第 j 个单词加入当前状态
newState := k | (1 << j)
// 如果以第 j 个单词结尾，在新状态下的接龙序列长度小于以第 i 个单词结尾，在当前状态下的接龙序列长度加上第 j 个单词的长度
if dp[j][newState] < dp[i][k]+len(words[j]) {
// 更新以第 j 个单词结尾，在新状态下的接龙序列长度
dp[j][newState] = dp[i][k] + len(words[j])
// 记录第 j 个单词在新状态下的前一个单词的索引为 i
pre[j][newState] = i
}
// 如果新状态下的接龙序列长度大于之前记录的最长长度
if size < dp[j][newState] {
// 更新最长长度
size = dp[j][newState]
// 更新最长接龙序列的最后一个单词的索引
index = j
// 更新最长接龙序列对应的状态
state = newState
}
}
}
}
// 用于存储最终的最长接龙序列
res := make([]string, 0, n)
// 回溯路径，构建最长接龙序列
for i := 0; i < n; i++ {
// 将当前单词加入结果列表
res = append(res, words[index])
// 更新当前单词的索引为前一个单词的索引
index = pre[index][state]
// 从状态中移除当前单词
state = state ^ (1 << index)
// 如果所有单词都已经处理完毕，则退出循环
if state == 0 {
break
}
}
// 由于回溯得到的结果是逆序的，所以需要反转结果列表
slices.Reverse(res)
return res
}
复杂度分析
类似的问题：TSP旅行商问题