单词接龙问题在GFG与LeetCode上运行差异的原因排查

需求是输出所有从beginWord到endWord的最短长度字符串序列。你提供的C++代码在GFG运行正常，但在LeetCode上失效，问题出在层级单词的管理逻辑上，以下是具体分析和修复方案：

原代码的核心问题 #

• 层级单词管理错误：原代码中usedOnLevel持续累加所有层的单词，进入下一层时会误删当前层未处理的同层单词——同一层的不同路径可以共享中间单词，不能提前从集合中移除。
• 未终止非最短路径处理：找到endWord后，未标记最短路径长度，后续更长的路径仍会继续处理，既浪费资源又可能引入错误结果。
• 层级清理逻辑混乱：每次进入新层级时未清空usedOnLevel，旧单词残留会干扰后续层的判断。

修复后的代码 #

class Solution {
public:
    vector<vector<string>> findSequences(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> st(wordList.begin(), wordList.end());
        queue<vector<string>> p;
        p.push({beginWord});
        vector<string> currentLevelWords; // 仅记录当前层使用的单词
        currentLevelWords.push_back(beginWord);
        int shortestLength = 0;
        vector<vector<string>> ans;

        while (!p.empty()) {
            vector<string> vec = p.front();
            p.pop();

            // 路径长度超过已找到的最短路径，直接跳过
            if (shortestLength != 0 && vec.size() > shortestLength) {
                break;
            }

            // 进入新层级时，删除上一层使用过的单词
            if (vec.size() > currentLevelWords.size()) {
                for (auto& word : currentLevelWords) {
                    st.erase(word);
                }
                currentLevelWords.clear();
            }

            string word = vec.back();
            // 找到目标单词，记录最短长度并加入结果
            if (word == endWord) {
                if (shortestLength == 0) {
                    shortestLength = vec.size();
                }
                ans.push_back(vec);
                continue; // 无需再扩展该路径
            }

            for (int i = 0; i < word.size(); ++i) {
                char original = word[i];
                for (char ch = 'a'; ch <= 'z'; ++ch) {
                    word[i] = ch;
                    if (st.find(word) != st.end()) {
                        currentLevelWords.push_back(word);
                        vec.push_back(word);
                        p.push(vec);
                        vec.pop_back();
                    }
                }
                word[i] = original;
            }
        }

        return ans;
    }
};

关键修改点 #

• 把usedOnLevel改为currentLevelWords，仅记录当前层使用的单词，进入新层级时清空并删除上一层单词，避免误删同层可用单词。
• 新增shortestLength变量，找到最短路径后，直接跳过后续更长的路径，终止无效计算。
• 找到endWord后直接continue，不再扩展该路径，减少不必要的运算。
• 调整层级判断逻辑，用vec.size() > currentLevelWords.size()准确识别层级变化，避免逻辑混乱。

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