leetcode 720. Longest Word in Dictionary 通过每次添加一个字符的最长单词计算

￡神魔★判官ぃ 2022-06-03 08:51 126阅读 0赞

Given a list of strings words representing an English Dictionary, find the longest word in words that can be built one character at a time by other words in words. If there is more than one possible answer, return the longest word with the smallest lexicographical order.

If there is no answer, return the empty string.  
Example 1:  
Input:  
words = \[“w”,”wo”,”wor”,”worl”, “world”\]  
Output: “world”  
Explanation:  
The word “world” can be built one character at a time by “w”, “wo”, “wor”, and “worl”.  
Example 2:  
Input:  
words = \[“a”, “banana”, “app”, “appl”, “ap”, “apply”, “apple”\]  
Output: “apple”  
Explanation:  
Both “apply” and “apple” can be built from other words in the dictionary. However, “apple” is lexicographically smaller than “apply”.  
Note:

All the strings in the input will only contain lowercase letters.  
The length of words will be in the range \[1, 1000\].  
The length of words\[i\] will be in the range \[1, 30\].

本题题意很简单，就是寻找一个字符串，它可以通过每次添加一个字符来得到我用的最笨的方法，直接暴力遍历，**注意为了降低计算量，我首先对字符串根据字符串的长度做了排序，然后依次判断是否可以依次构建，假如可以的话，只有得到的字符串要比你res里面的length大的话才加入判断，否者直接跳出**

代码如下：

#include <iostream>
    #include <vector>
    #include <map>
    #include <set>
    #include <queue>
    #include <stack>
    #include <string>
    #include <climits>
    #include <algorithm>
    #include <sstream>
    #include <functional>
    #include <bitset>
    #include <numeric>
    #include <cmath>
    #include <regex>
    
    using namespace std;
    
    
    bool cmp(string a, string b)
    {
        return a.length() > b.length();
    }
    class Solution 
    {
    public:
        string longestWord(vector<string>& words) 
        {
            sort(words.begin(), words.end(),cmp);
            set<string> ss(words.begin(), words.end());
    
            vector<string> res;
            for (string word : words)
            {
                int len = 1;
                for (len = 1; len <= word.length() - 1; len++)
                {
                    if (ss.find(word.substr(0, len)) == ss.end())
                        break;
                }
                if (len == word.length())
                {
                    if (res.size() == 0 || res.back().length() <= word.length())
                        res.push_back(word);
                    else
                        break;
                }
            }
    
            string a = res[0];
            for (string s : res)
                a = min(a, s);
            return a;
    
        }
    };