题目描述

给定一组单词words，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。若
有多个长度相同的结果，返回其中字典序最小的一项，若没有符合要求的单词则返回空字符串。
示例：
输入： [“cat”,“banana”,“dog”,“nana”,“walk”,“walker”,“dogwalker”]
输出： “dogwalker”
解释： "dogwalker"可由"dog"和"walker"组成。

代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>
#include <functional>

using namespace std;

bool cmp (const string& a, const string& b) {
    if (a.length() == b.length()) {
        return a < b;
    }
    return a.length() > b.length();
}

bool dfs(const string& target, int start, unordered_map<string, bool>& dict) {
    if (start == target.length()) {
        return true;
    }
    for (int i = start; i < target.length(); ++i) {
        if (i - start + 1 == target.length()) {
            continue;
        }
        if (dict.count(target.substr(start, i - start + 1))) {
            if (dfs(target, i + 1, dict)) {
                return true;
            }
        }
    }
    return false;
}

string longestWord(vector<string>& words) {
    sort(words.begin(), words.end(), cmp);

    unordered_map<string, bool> dict;
    for (const string& word : words) {
        dict[word] = true;
    }

    for (const string& word : words) {
        if (dfs(word, 0, dict)) {
            return word;
        }
    }

    return "";
}

int main() {
    vector<string> words = {"banana", "app", "apple", "bananaapple", "bananaappleapple"};
    string result = longestWord(words);
    cout << "Longest word: " << result << endl;
    return 0;
}