题目描述

image-20221215165645334

思路分析

回溯

  • 最开始没想到思路，然后看了一眼提示

  • 提示

    • 简化题目，如果要求的字符串只由两个其他的字符串构成，解法：枚举两两可能性
    • 扩展到多个字符串，解法：寻找分割点

  • 首先将字符串数组排序：毕竟是求最长的，找到就不找了

    • 长度相等，字典序小的在前
    • 长度不等，长度长的在前

  • 将字符串存入hash表mp，方便查找

  • 遍历字符串数组，寻找可能的解

  • 对于字符串数组中的每一个值

    • 都回溯找一下是否能得到答案
    • 按长度递减找分割点，分成两份，即cur和next
      • 如果cur在mp中，继续判断next
      • 如果不在，直接寻找下一个分割点
      • 按长度递减是因为
        • 如果长的满足，且后续满足就不要考虑短的；如果长的不满足，还有机会考虑长的
        • 反之，如果先考虑短的，就不存在计划考虑长的了，至少下面的代码不能
        • 如用例["cat","banana","dog","nana","walk","walker","dogwalker"]
    • 如果找到一个值，退出循环，直接返回结果

  • 注意回溯的退出条件时，剩余的串为空

  • 为了避免找到由自身构成的最长串，还需要一个额外的变量记录cnt当前使用的字符串数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
private:
    bool process(string& word, unordered_set<string>& mp, int cnt) {
        // 寻找分割点
        // 判断剩余串是否存在，如果都存在，即为true
        // 需要有回溯的过程
        if (word.empty()) return true;
        int n = word.size();
        // 逆向，从长往短找
        for (int i = n; i >= 1; i--) {
            string cur = word.substr(0, i);
            string next = word.substr(i);
            // cout << "word : " << word << ", cur : " << cur << ", next : " << next << endl;
            if (mp.count(cur)) {
                // walk 和 walker 
                cnt += 1;
                if (process(next, mp, cnt) && cnt > 1) {
                    return true;
                }
            }
        }

        return false;
    }

public:
    string longestWord(vector<string>& words) {
        sort(words.begin(), words.end(),[](string& a, string& b){
            return a.size() == b.size() ? a < b : a.size() > b.size();
        });
        unordered_set<string> mp;
        for (auto& word : words) mp.insert(word);
        for (auto& word : words) {
            if (process(word, mp, 0)) {
                return word;
            }
        }

        return "";
    }
};

image-20221215170559606