如何用C++实现单词首尾字母匹配的重排功能？

问题描述 #

给定每行一个单词的小写单词列表，需要重排单词顺序，满足：

• 除第一个单词外，每个单词的首字母与前一个单词的尾字母相同
• 所有单词必须被使用，每个单词恰好使用一次（重复单词按出现次数使用）

问题建模 #

这个问题本质是欧拉路径问题：

• 将每个字母（a-z）视为图的节点
• 将每个单词视为一条从首字母指向尾字母的边
• 我们需要找到一条遍历所有边恰好一次的路径，对应单词的接龙顺序

算法思路 #

采用深度优先搜索（DFS）+ 回溯的方式实现，结合图的欧拉路径判定规则：

1. 图构建：
   • 统计每个字母的入度、出度
   • 用映射表记录每个起始字母对应的单词列表（用链表结构处理重复单词）
2. 路径存在性判定：
   • 合法情况1：所有字母的入度等于出度
   • 合法情况2：恰好一个字母出度比入度大1（作为路径起点），一个字母入度比出度大1（作为路径终点），其余字母入度等于出度
3. DFS回溯求解：
   • 从起始节点出发，递归选择当前节点可使用的单词，标记已使用，直到所有单词都被加入路径

C++代码实现 #

#include <iostream>
#include <vector>
#include <unordered_map>
#include <string>
#include <list>

using namespace std;

// 邻接表：记录每个起始字母对应的单词列表
unordered_map<char, list<string>> adj;
// 统计每个字母的入度和出度
unordered_map<char, int> in_degree, out_degree;
vector<string> result;
int total_words = 0;

// DFS回溯寻找合法路径
bool dfs(char current) {
    if (result.size() == total_words) {
        return true;
    }

    auto& words = adj[current];
    for (auto it = words.begin(); it != words.end(); ) {
        string word = *it;
        // 临时删除当前单词，避免重复使用
        it = words.erase(it);
        result.push_back(word);
        char next_char = word.back();
        if (dfs(next_char)) {
            return true;
        }
        // 回溯：恢复单词到邻接表
        words.insert(it, word);
        result.pop_back();
    }
    return false;
}

int main() {
    string word;
    // 读取输入，每行一个单词
    while (getline(cin, word)) {
        if (word.empty()) continue;
        char start = word.front();
        char end = word.back();
        adj[start].push_back(word);
        out_degree[start]++;
        in_degree[end]++;
        total_words++;
    }

    // 确定起始节点
    char start_node = ' ';
    int out_more = 0, in_more = 0;
    for (auto& pair : out_degree) {
        char c = pair.first;
        int diff = out_degree[c] - in_degree[c];
        if (diff == 1) {
            start_node = c;
            out_more++;
        } else if (diff == -1) {
            in_more++;
        } else if (diff != 0) {
            cout << "No valid sequence exists." << endl;
            return 0;
        }
    }
    // 所有入度等于出度时，选第一个有出度的节点作为起点
    if (out_more == 0 && in_more == 0) {
        for (auto& pair : adj) {
            if (!pair.second.empty()) {
                start_node = pair.first;
                break;
            }
        }
    }
    // 检查是否符合欧拉路径的合法条件
    if (!((out_more == 0 && in_more == 0) || (out_more == 1 && in_more == 1))) {
        cout << "No valid sequence exists." << endl;
        return 0;
    }

    // 执行DFS寻找路径
    if (start_node != ' ' && dfs(start_node)) {
        for (const string& w : result) {
            cout << w << endl;
        }
    } else {
        cout << "No valid sequence exists." << endl;
    }

    return 0;
}

代码说明 #

• 使用list<string>存储每个起始字母对应的单词，便于回溯时快速删除和恢复元素
• 入度出度统计用于提前判断是否存在合法路径，避免无效搜索
• 回溯过程中通过动态修改邻接表，确保每个单词被恰好使用一次
• 天然支持重复单词的处理，因为链表会保留重复的单词条目

内容的提问来源于stack exchange，提问作者ravenspoint