LeetCode/leetcode/720/s1.cpp at master · lzl124631x/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// OJ: https://leetcode.com/problems/longest-word-in-dictionary/
// Author: github.com/lzl124631x
// Time: O(NW)
// Space: O(Nw)
class Solution {
public:
    string longestWord(vector<string>& words) {
        unordered_set<string> s;
        for (auto &w : words) s.insert(w);
        string ans;
        for (auto &w : words) {
            if (w.size() < ans.size()) continue;
            auto x = w;
            do {
                x.pop_back();
            } while (x.size() && s.find(x) != s.end());
            if (x.size()) continue;
            if (w.size() > ans.size()
               || (w.size() == ans.size() && w < ans)) ans = w;
        }
        return ans;
    }
};