刷题笔记合集🔗

单词接龙

问题描述

单词接龙的规则是：

• 可用于接龙的单词首字母必须要与前一个单词的尾字母相同；
• 当存在多个首字母相同的单词时，取长度最长的单词，如果长度也相等，则取字典序最小的单词；已经参与接龙的单词不能重复使用。
• 现给定一组全部由小写字母组成单词数组，并指定其中的一个单词作为起始单词，进行单词接龙，
• 请输出最长的单词串，单词串是单词拼接而成，中间没有空格。

输入格式

• 输入的第一行为一个非负整数，表示起始单词在数组中的索引 ， ；
• 输入的第二行为一个非负整数，表示单词的个数 ；
• 接下来的 行，分别表示单词数组中的单词。

备注：

• 单词个数 的取值范围为 ；
• 单个单词的长度的取值范围为 。

输出格式

• 输出一个字符串，表示最终拼接的单词串。

样例输入

0
6
word
dd
da
dc
dword
d

4
6
word
dd
da
dc
dword
d

样例输出

worddwordda

dwordda

数据范围

• 
• 
• 单个单词的长度
• 所有单词均由小写字母组成

题解

这道题目是一个单词接龙问题，要求我们按照特定规则构建一个单词链。

首先，我们需要从给定的一个起始位置的单词开始，然后按照以下规则进行接龙：

1. 下一个单词的首字母必须和当前单词的尾字母相同
2. 当有多个候选单词时，优先选择长度最长的单词
3. 如果长度相同，则选择字典序最小的单词
4. 已经使用过的单词不能再次使用

解题思路：

1. 首先，我将起始单词加入结果链中，并将其从可用单词列表中移除
2. 然后，构建一个按首字母分类的单词集合，这样可以快速找到以特定字母开头的单词
3. 对每个字母开头的单词集合进行排序，按照长度降序和字典序升序的优先级
4. 循环处理，每次查找当前单词链尾单词的末尾字母，寻找以该字母开头的下一个可用单词
5. 如果找到合适的单词，则将其添加到链中并从可用集合移除
6. 如果找不到合适的单词，则结束接龙过程

这种方法的时间复杂度主要由排序操作决定。假设有n个单词，平均长度为m，那么排序的复杂度是O(n log n)，字符串比较的复杂度是O(m)，所以总体时间复杂度为O(m×n log n)。在最坏情况下，我们可能需要遍历所有单词，因此复杂度为O(n)，综合来看为O(m×n log n)。

在给定的数据范围(N≤20，单词长度≤30)内，这个复杂度是完全可接受的。

参考代码

• Python

import sys

# 定义输入函数
input = lambda: sys.stdin.readline().strip()

# 读取输入
k = int(input())  # 起始单词索引
n = int(input())  # 单词个数
words = [input() for _ in range(n)]  # 读取所有单词

def find_longest_chain():
    # 创建单词链，从起始单词开始
    chain = [words[k]]
    
    # 从单词列表中移除起始单词
    avail_words = words.copy()
    avail_words.pop(k)
    
    # 按首字母分组单词
    first_char_groups = {}
    for w in avail_words:
        if w[0] not in first_char_groups:
            first_char_groups[w[0]] = []
        first_char_groups[w[0]].append(w)
    
    # 对每个首字母组内的单词排序：先按长度降序，再按字典序升序
    for ch in first_char_groups:
        first_char_groups[ch].sort(key=lambda x: (-len(x), x))
    
    # 开始接龙
    while True:
        # 获取当前链尾单词的最后一个字母
        last_char = chain[-1][-1]
        
        # 查找以该字母开头的可用单词
        if last_char in first_char_groups and first_char_groups[last_char]:
            # 取长度最长且字典序最小的单词
            next_word = first_char_groups[last_char][0]
            chain.append(next_word)
            
            # 从可用单词中移除已使用的单词
            first_char_groups[last_char].remove(next_word)
        else:
            # 不存在可用的接龙单词，结束
            break
    
    # 返回拼接的单词串
    return "".join(chain)

# 输出结果
print(find_longest_chain())

• Cpp

#include <bits/stdc++.h>
using namespace std;

int main() {
    int k, n;
    cin >> k >> n;
    
    vector<string> words(n);
    for (int i = 0; i < n; i++) {
        cin >> words[i];
    }
    
    // 创建单词链，从起始单词开始
    vector<stri