import java.util.HashSet;
import java.util.Set;

/**

 720. Longest Word in Dictionary

 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].

 @tag-trie

 */

public class Longest_Word_in_Dictionary {

    // add full implementation for visibility
    class Solution_Trie {

        public String longestWord(String[] words) {

            if (words == null || words.length == 0) {
                return "";
            }

            String result = "";
            Trie wordTrie = new Trie();

            for (String word: words) {
                wordTrie.insert(word);
            }

            for (String word: words) {

                // && higher than ||
                if (word.length() > result.length() || word.length() == result.length() && word.compareTo(result) < 0) {
                    boolean good = true;
                    for (int k = 1; k < word.length(); ++k) {
                        if (!wordTrie.search(word.substring(0, k))) {
                            good = false;
                            break;
                        }
                    }
                    if (good) {
                        result = word;
                    }
                }
            }
            return result;
        }

        class Trie {

            // just remember, root is the very top of this tree, all starts at root's children-array
            public TrieNode root = new TrieNode();

            // @note:@memorize: iteration is better than recursion during trie building
            public void insert(String word) {
                TrieNode node = root;
                for (char c : word.toCharArray()) {
                    if (node.children[c - 'a'] == null) {
                        node.children[c - 'a'] = new TrieNode();
                    }
                    node = node.children[c - 'a'];
                }
                node.item = word;
            }

            public boolean search(String word) {
                TrieNode node = root;
                for (char c : word.toCharArray()) {
                    if (node.children[c - 'a'] == null)
                        return false;
                    node = node.children[c - 'a'];
                }
                if (node.item.equals(word)) {
                    return true;
                } else {
                    return false;
                }
            }

            public boolean startsWith(String prefix) {
                TrieNode node = root;
                for (char c : prefix.toCharArray()) {
                    if (node.children[c - 'a'] == null)
                        return false;
                    node = node.children[c - 'a'];
                }
                return true;
            }
        }

        class TrieNode {

            // maybe 26 is not sufficient enough...I would make it 256 for general usage
            // public TrieNode[] children = new TrieNode[26];
            public TrieNode[] children = new TrieNode[256];

            public String item = "";

        }
    }

    class Solution {
        public String longestWord(String[] words) {

            if (words == null || words.length == 0) {
                return "";
            }

            String result = "";
            Set<String> wordset = new HashSet();

            for (String word: words) {
                wordset.add(word);
            }

            for (String word: words) {

                // && higher than ||
                if (word.length() > result.length() || word.length() == result.length() && word.compareTo(result) < 0) {
                    boolean good = true;
                    for (int k = 1; k < word.length(); ++k) {
                        if (!wordset.contains(word.substring(0, k))) {
                            good = false;
                            break;
                        }
                    }
                    if (good) result = word;
                }
            }
            return result;
        }
    }

}

############

class Solution {
    private Set<String> s;

    public String longestWord(String[] words) {
        s = new HashSet<>(Arrays.asList(words));
        int cnt = 0;
        String ans = "";
        for (String w : s) {
            int n = w.length();
            if (check(w)) {
                if (cnt < n) {
                    cnt = n;
                    ans = w;
                } else if (cnt == n && w.compareTo(ans) < 0) {
                    ans = w;
                }
            }
        }
        return ans;
    }

    private boolean check(String word) {
        for (int i = 1, n = word.length(); i < n; ++i) {
            if (!s.contains(word.substring(0, i))) {
                return false;
            }
        }
        return true;
    }
}

// OJ: https://leetcode.com/problems/longest-word-in-dictionary/
// 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;
    }
};

class Solution:
    def longestWord(self, words: List[str]) -> str:
        cnt, ans = 0, ''
        s = set(words)
        for w in s:
            n = len(w)
            if all(w[:i] in s for i in range(1, n)):
                if cnt < n:
                    cnt, ans = n, w
                elif cnt == n and w < ans:
                    ans = w
        return ans

############

class Solution(object):
    def longestWord(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        wset = set(words)
        res = ""
        for w in words:
            isIn = True
            for i in range(1, len(w)):
                if w[:i] not in wset:
                    isIn = False
                    break
            if isIn:
                if not res or len(w) > len(res):
                    res = w
                elif len(w) == len(res) and res > w:
                    res = w
        return res

func longestWord(words []string) string {
	s := make(map[string]bool)
	for _, w := range words {
		s[w] = true
	}
	cnt := 0
	ans := ""
	check := func(word string) bool {
		for i, n := 1, len(word); i < n; i++ {
			if !s[word[:i]] {
				return false
			}
		}
		return true
	}
	for w, _ := range s {
		n := len(w)
		if check(w) {
			if cnt < n {
				cnt, ans = n, w
			} else if cnt == n && w < ans {
				ans = w
			}
		}
	}
	return ans
}

function longestWord(words: string[]): string {
    words.sort((a, b) => {
        const n = a.length;
        const m = b.length;
        if (n === m) {
            return a < b ? -1 : 1;
        }
        return m - n;
    });
    for (const word of words) {
        let isPass = true;
        for (let i = 1; i <= word.length; i++) {
            if (!words.includes(word.slice(0, i))) {
                isPass = false;
                break;
            }
        }
        if (isPass) {
            return word;
        }
    }
    return '';
}

impl Solution {
    pub fn longest_word(mut words: Vec<String>) -> String {
        words.sort_unstable_by(|a, b| (b.len(), a).cmp(&(a.len(), b)));
        for word in words.iter() {
            let mut is_pass = true;
            for i in 1..=word.len() {
                if !words.contains(&word[..i].to_string()) {
                    is_pass = false;
                    break;
                }
            }
            if is_pass {
                return word.clone();
            }
        }
        String::new()
    }
}

class Solution {
    public String longestWord(String[] words) {
        Arrays.sort(words);
        String longestWord = "";
        int maxLength = 0;
        Set<String> set = new HashSet<String>();
        int length = words.length;
        for (int i = 0; i < length; i++) {
            String word = words[i];
            int wordLength = word.length();
            if (wordLength == 1 || set.contains(word.substring(0, wordLength - 1))) {
                if (wordLength > maxLength || wordLength == maxLength && word.compareTo(longestWord) < 0) {
                    longestWord = word;
                    maxLength = wordLength;
                }
                set.add(word);
            }
        }
        return longestWord;
    }
}

############

class Solution {
    private Set<String> s;

    public String longestWord(String[] words) {
        s = new HashSet<>(Arrays.asList(words));
        int cnt = 0;
        String ans = "";
        for (String w : s) {
            int n = w.length();
            if (check(w)) {
                if (cnt < n) {
                    cnt = n;
                    ans = w;
                } else if (cnt == n && w.compareTo(ans) < 0) {
                    ans = w;
                }
            }
        }
        return ans;
    }

    private boolean check(String word) {
        for (int i = 1, n = word.length(); i < n; ++i) {
            if (!s.contains(word.substring(0, i))) {
                return false;
            }
        }
        return true;
    }
}

// OJ: https://leetcode.com/problems/longest-word-in-dictionary/
// 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;
    }
};

class Solution:
    def longestWord(self, words: List[str]) -> str:
        cnt, ans = 0, ''
        s = set(words)
        for w in s:
            n = len(w)
            if all(w[:i] in s for i in range(1, n)):
                if cnt < n:
                    cnt, ans = n, w
                elif cnt == n and w < ans:
                    ans = w
        return ans

############

class Solution(object):
    def longestWord(self, words):
        """
        :type words: List[str]
        :rtype: str
        """
        wset = set(words)
        res = ""
        for w in words:
            isIn = True
            for i in range(1, len(w)):
                if w[:i] not in wset:
                    isIn = False
                    break
            if isIn:
                if not res or len(w) > len(res):
                    res = w
                elif len(w) == len(res) and res > w:
                    res = w
        return res

func longestWord(words []string) string {
	s := make(map[string]bool)
	for _, w := range words {
		s[w] = true
	}
	cnt := 0
	ans := ""
	check := func(word string) bool {
		for i, n := 1, len(word); i < n; i++ {
			if !s[word[:i]] {
				return false
			}
		}
		return true
	}
	for w, _ := range s {
		n := len(w)
		if check(w) {
			if cnt < n {
				cnt, ans = n, w
			} else if cnt == n && w < ans {
				ans = w
			}
		}
	}
	return ans
}

function longestWord(words: string[]): string {
    words.sort((a, b) => {
        const n = a.length;
        const m = b.length;
        if (n === m) {
            return a < b ? -1 : 1;
        }
        return m - n;
    });
    for (const word of words) {
        let isPass = true;
        for (let i = 1; i <= word.length; i++) {
            if (!words.includes(word.slice(0, i))) {
                isPass = false;
                break;
            }
        }
        if (isPass) {
            return word;
        }
    }
    return '';
}

impl Solution {
    pub fn longest_word(mut words: Vec<String>) -> String {
        words.sort_unstable_by(|a, b| (b.len(), a).cmp(&(a.len(), b)));
        for word in words.iter() {
            let mut is_pass = true;
            for i in 1..=word.len() {
                if !words.contains(&word[..i].to_string()) {
                    is_pass = false;
                    break;
                }
            }
            if is_pass {
                return word.clone();
            }
        }
        String::new()
    }
}

720 - Longest Word in Dictionary

All Problems

All Solutions

Welcome to Subscribe On Youtube

All Problems

All Solutions