Leetcode720.Longest Word in Dictionary词典中最长的单词

给出一个字符串数组words组成的一本英语词典。从中找出最长的一个单词，该单词是由words词典中其他单词逐步添加一个字母组成。若其中有多个可行的答案，则返回答案中字典序最小的单词。

若无答案，则返回空字符串。

示例 1:

输入: words = ["w","wo","wor","worl", "world"] 输出: "world" 解释: 单词"world"可由"w", "wo", "wor", 和 "worl"添加一个字母组成。

示例 2:

输入: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"] 输出: "apple" 解释: "apply"和"apple"都能由词典中的单词组成。但是"apple"得字典序小于"apply"。

注意:

所有输入的字符串都只包含小写字母。
words数组长度范围为[1,1000]。
words[i]的长度范围为[1,30]。

bool cmp1(string a, string b)

{

    return a.size() > b.size();

}

bool cmp2(string a, string b)

{

    return a < b;

}

class Solution {

public:

    string longestWord(vector<string>& words) {

        int len = words.size();

        if(len <= 1)

            return len == 0? "":words[0];

        vector<string> res;

        map<string, int> check;

        for(int i = 0; i < len; i++)

        {

            check[words[i]] = 1;

        }

        sort(words.begin(), words.end(), cmp1);

        int MAXsize = 0;

        for(int i = 0; i < len; i++)

        {

            int size = words[i].size();

            bool flag = true;

            if(MAXsize != 0 && MAXsize > size)

                continue;

            for(int j = 0; j < size - 1; j++)

            {

                string temp = "";

                for(int k = 0; k <= j; k++)

                {

                    temp += words[i][k];

                }

                if(check[temp] != 1)

                {

                    flag = false;

                    break;

                }

            }

            if(flag == true)

            {

                MAXsize = max(MAXsize, size);

                res.push_back(words[i]);

            }

        }

        if(res.size() == 0)

            return "";

        sort(res.begin(), res.end(), cmp2);

        return res[0];

    }

};

巴特西

Leetcode720.Longest Word in Dictionary词典中最长的单词

最新文章

热门文章