package leetcode;

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

/**
 * https://leetcode.com/problems/longest-word-in-dictionary/
 */
public class Problem720 {
    public String longestWord(String[] words) {
        Arrays.sort(words, (a, b) -> {
            int cmp = Integer.compare(b.length(), a.length());
            if (cmp == 0) {
                return a.compareTo(b);
            }
            return cmp;
        });
        Set<String> set = new HashSet<>();
        for (String word : words) {
            set.add(word);
        }
        for (String word : words) {
            boolean found = true;
            String tmp = "";
            for (int i = 0; i < word.length(); i++) {
                tmp += word.charAt(i);
                if (!set.contains(tmp)) {
                    found = false;
                    break;
                }
            }
            if (found) {
                return word;
            }
        }
        return "";
    }

    public static void main(String[] args) {
        Problem720 prob = new Problem720();
        System.out.println(prob.longestWord(new String[]{"w","wo","wor","worl", "world"})); // world
        System.out.println(prob.longestWord(new String[]{"a", "banana", "app", "appl", "ap", "apply", "apple"})); // apple
        System.out.println(prob.longestWord(new String[]{"a"})); // a
        System.out.println(prob.longestWord(new String[]{"a", "b"})); // a
        System.out.println(prob.longestWord(new String[]{"m", "mo", "moc", "moch", "mocha", "l", "la", "lat", "latt", "latte", "c", "ca", "cat"})); // latte
        System.out.println(prob.longestWord(new String[]{"ogz","eyj","e","ey","hmn","v","hm","ogznkb","ogzn","hmnm","eyjuo","vuq","ogznk","og","eyjuoi","d"})); // eyj
        System.out.println(prob.longestWord(new String[]{"yo","ew","fc","zrc","yodn","fcm","qm","qmo","fcmz","z","ewq","yod","ewqz","y"})); // yodn
        System.out.println(prob.longestWord(new String[]{"rac","rs","ra","on","r","otif","o","onpdu","rsf","rs","ot","oti","racy","onpd"})); // otif
    }
}

@@ -16,33 +16,8 @@
 e;%0A%0A
-import java.util.Arrays;%0A
 impo
@@ -208,227 +208,8 @@
 ) %7B%0A
-        Arrays.sort(words, (a, b) -%3E %7B%0A            int cmp = Integer.compare(b.length(), a.length());%0A            if (cmp == 0) %7B%0A                return a.compareTo(b);%0A            %7D%0A            return cmp;%0A        %7D);%0A
     
@@ -312,32 +312,60 @@
 ord);%0A        %7D%0A
+        String result = %22%22;%0A
         for (Str
@@ -721,20 +721,46 @@
     
-return word;
+if (word.length() %3E result.length()) %7B
 %0A   
@@ -768,26 +768,24 @@
         
-%7D%0A
         
 %7D%0A      
@@ -780,1114 +780,265 @@
     
-%7D%0A        return %22%22;%0A    %7D%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem720 prob = new Problem720();%0A        System.out.println(prob.longestWord(new String%5B%5D%7B%22w%22,%22wo%22,%22wor%22,%22worl%22, %22world%22%7D)); // world%0A        System.out.println(prob.longestWord(new String%5B%5D%7B%22a%22, %22banana%22, %22app%22, %22appl%22, %22ap%22, %22apply%22, %22apple%22%7D)); // apple%0A        System.out.println(prob.longestWord(new String%5B%5D%7B%22a%22%7D)); // a%0A        System.out.println(prob.longestWord(new String%5B%5D%7B%22a%22, %22b%22%7D)); // a%0A
+result = word;%0A                %7D else if (word.length() == result.length()) %7B%0A                    if (word.compareTo(result) %3C 0) %7B%0A                        result = word;%0A               
      
+%7D%0A
    
-System.out.println(prob.longestWord(new String%5B%5D%7B%22m%22, %22mo%22, %22moc%22, %22moch%22, %22mocha%22, %22l%22, %22la%22, %22lat%22, %22latt%22, %22latte%22, %22c%22, %22ca%22, %22cat%22%7D)); // latte%0A        System.out.println(prob.longestWord(new String%5B%5D%7B%22ogz%22,%22eyj%22,%22e%22,%22ey%22,%22hmn%22,%22v%22,%22hm%22,%22ogznkb%22,%22ogzn%22,%22hmnm%22,%22eyjuo%22,%22vuq%22,%22ogznk%22,%22og%22,%22eyjuoi%22,%22d%22%7D)); // eyj%0A        System.out.println(prob.longestWord(new String%5B%5D%7B%22yo%22,%22ew%22,%22fc%22,%22zrc%22,%22yodn%22,%22fcm%22,%22qm%22,%22qmo%22,%22fcmz%22,%22z%22,%22ewq%22,%22yod%22,%22ewqz%22,%22y%22%7D)); // yodn%0A        System.out.println(prob.longestWord(new String%5B%5D%7B%22rac%22,%22rs%22,%22ra%22,%22on%22,%22r%22,%22otif%22,%22o%22,%22onpdu%22,%22rsf%22,%22rs%22,%22ot%22,%22oti%22,%22racy%22,%22onpd%22%7D)); // otif
+             %7D%0A            %7D%0A        %7D%0A        return result;
 %0A   

Solve problem 720