问题理解

我们需要从给定的单词列表中找到最长的链，其中每个单词是前一个单词的“混合扩展”。一个单词 A 是另一个单词 B 的“混合扩展”，如果 A 可以通过在 B 中添加一个字母并重新排列得到。例如，"ab", "bar", "crab", "cobra", 和 "carbon" 形成一个长度为 5 的链。

解决思路

输入处理：读取输入的单词列表。 预处理：计算每个单词的字符频率（哈希），这将帮助我们快速判断一个单词是否是另一个单词的“混合扩展”。 排序：按单词长度排序，以便我们可以从短到长处理单词。 动态规划： 使用动态规划来计算以每个单词结尾的最长链长度。 对于每个单词，检查所有比它短一个字母的单词，看看它们是否是“混合扩展”。 如果是，则更新当前单词的最长链长度和前驱索引。 输出：根据动态规划结果，输出最长链。

代码实现

以下是完整的 C++ 代码实现：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
 
using namespace std;
 
struct Word {
    char str[25];
    int hash[26] = {0};
    int len;
    int dp = 1;
    int pre = -1;
    
    void calculate_hash() {
        len = strlen(str);
        for (int i = 0; i < len; i++) {
            hash[str[i] - 'a']++;
        }
    }
    
    void print() const {
        printf("%s\n", str);
    }
};
 
bool compare_length(const Word& a, const Word& b) {
    return a.len < b.len;
}
 
void print_chain(const vector<Word>& words, int index) {
    if (index == -1) return;
    print_chain(words, words[index].pre);
    words[index].print();
}
 
int main() {
    vector<Word> words;
    char buffer[25];
    
    // 读取输入
    while (scanf("%s", buffer) != EOF) {
        Word word;
        strcpy(word.str, buffer);
        word.calculate_hash();
        words.push_back(word);
    }
    
    // 按长度排序
    sort(words.begin(), words.end(), compare_length);
    
    int max_index = 0;
    int max_length = 1;
    
    // 动态规划处理
    for (int i = 1; i < words.size(); i++) {
        for (int j = i - 1; j >= 0; j--) {
            // 只检查长度小1的单词
            if (words[j].len + 1 < words[i].len) break;
            if (words[j].len != words[i].len - 1) continue;
            
            int diff = 0;
            for (int k = 0; k < 26; k++) {
                diff += abs(words[i].hash[k] - words[j].hash[k]);
                if (diff > 2) break; // 提前终止
            }
            
            if (diff <= 2 && words[i].dp < words[j].dp + 1) {
                words[i].dp = words[j].dp + 1;
                words[i].pre = j;
                
                if (words[i].dp > max_length) {
                    max_length = words[i].dp;
                    max_index = i;
                }
            }
        }
    }
    
    // 输出最长链
    print_chain(words, max_index);
    
    return 0;
}

代码解释

Word 结构体： str：存储单词字符串。 hash：存储每个字母的频率。 len：单词长度。 dp：以当前单词结尾的最长链长度。 pre：前驱单词的索引。 calculate_hash()：计算单词的字母频率。 print()：打印单词。 compare_length：用于按单词长度排序的比较函数。 print_chain：递归打印最长链。 main 函数： 读取输入并存储到 words 向量中。 按单词长度排序。 使用动态规划计算最长链。 输出最长链。 动态规划部分详解 对于每个单词 i，检查所有比它短一个字母的单词 j。 计算 i 和 j 的字母频率差。如果差不超过 2（因为添加一个字母最多改变两个字母的频率），则 i 可以是 j 的“混合扩展”。 更新 i 的最长链长度和前驱索引。 跟踪最长链的结束索引 max_index 和长度 max_length。 输出部分 使用递归函数 print_chain 从最长链的结束索引开始，回溯打印整个链。