Skip to content

Latest commit

 

History

History
88 lines (72 loc) · 2.95 KB

README.md

File metadata and controls

88 lines (72 loc) · 2.95 KB

Given an array of strings words, find the longest string in words such that every prefix of it is also in words.

  • For example, let words = ["a", "app", "ap"]. The string "app" has prefixes "ap" and "a", all of which are in words.

Return the string described above. If there is more than one string with the same length, return the lexicographically smallest one, and if no string exists, return "".

 

Example 1:

Input: words = ["k","ki","kir","kira", "kiran"]
Output: "kiran"
Explanation: "kiran" has prefixes "kira", "kir", "ki", and "k", and all of them appear in words.

Example 2:

Input: words = ["a", "banana", "app", "appl", "ap", "apply", "apple"]
Output: "apple"
Explanation: Both "apple" and "apply" have all their prefixes in words.
However, "apple" is lexicographically smaller, so we return that.

Example 3:

Input: words = ["abc", "bc", "ab", "qwe"]
Output: ""

 

Constraints:

  • 1 <= words.length <= 105
  • 1 <= words[i].length <= 105
  • 1 <= sum(words[i].length) <= 105

Companies:
Google

Related Topics:
Depth-First Search, Trie

Similar Questions:

Solution 1. Trie

// OJ: https://leetcode.com/problems/longest-word-with-all-prefixes/
// Author: github.com/lzl124631x
// Time: O(NW)
// Space: O(NW)
struct TrieNode {
    TrieNode *next[26] = {};
    bool word = false;
};
class Solution {
    void addWord(TrieNode *node, string &s) {
        for (char c : s) {
            if (!node->next[c - 'a']) node->next[c - 'a'] = new TrieNode();
            node = node->next[c - 'a'];
        }
        node->word = true;
    }
    string ans, path;
    void dfs(TrieNode *node) {
        for (int i = 0; i < 26; ++i) {
            if (!node->next[i] || !node->next[i]->word) continue;
            path += 'a' + i;
            if (path.size() > ans.size()) ans = path;
            dfs(node->next[i]);
            path.pop_back();
        }
    }
public:
    string longestWord(vector<string>& A) {
        TrieNode root;
        for (auto &s : A) addWord(&root, s);
        dfs(&root);
        return ans;
    }
};