package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * https://leetcode.com/problems/longest-word-in-dictionary/
 */
public class Problem720 {
    public String longestWord(String[] words) {
        Arrays.sort(words, (a, b) -> a.compareTo(b));
        String tmp = "";
        List<String> result = new ArrayList<>();
        for (int i = 0; i < words.length; i++) {
            if (words[i].length() == 1) {
                if (!tmp.isEmpty()) {
                    result.add(tmp);
                }
                tmp = words[i];
            } else {
                if (tmp.length() + 1 == words[i].length() && words[i].startsWith(tmp)) {
                    tmp = words[i];
                }
            }
        }
        result.add(tmp);
        result.sort((a, b) -> {
            if (a.length() < b.length()) {
                return 1;
            } else if (a.length() > b.length()) {
                return -1;
            } else {
                return a.compareTo(b);
            }
        });
        return result.get(0);
    }

    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
    }
}

@@ -34,20 +34,17 @@
 il.Array
-List
+s
 ;%0Aimport
@@ -46,38 +46,39 @@
 mport java.util.
-Arrays
+HashSet
 ;%0Aimport java.ut
@@ -80,19 +80,18 @@
 va.util.
-Lis
+Se
 t;%0A%0A/**%0A
@@ -270,186 +270,97 @@
  -%3E 
-a.compareTo(b));%0A        String tmp = %22%22;%0A        List%3CString%3E result = new ArrayList%3C%3E();%0A        for (int i = 0; i %3C words.length; i++) %7B%0A            if (words%5Bi%5D.length()
+%7B%0A            int cmp = Integer.compare(b.length(), a.length());%0A            if (cmp
  == 
-1
+0
 ) %7B%0A
@@ -379,30 +379,32 @@
     
-if (!tmp.isEmpty()) %7B%0A
+return a.compareTo(b);%0A 
     
@@ -401,32 +401,35 @@
 (b);%0A           
+ %7D%0A
           result
@@ -418,39 +418,36 @@
 %7D%0A          
-result.add(t
+  return c
 mp
-)
 ;%0A          
@@ -448,49 +448,90 @@
     
-  
+%7D);%0A
       
-%7D%0A                tmp =
+  Set%3CString%3E set = new HashSet%3C%3E();%0A        for (String word :
  words
-%5Bi%5D;
+) %7B
 %0A   
@@ -535,32 +535,38 @@
             
-%7D else %7B
+set.add(word);
 %0A           
@@ -558,32 +558,34 @@
 d);%0A        
+%7D%0A
         
 if (tmp.leng
@@ -576,340 +576,314 @@
     
-if (tmp.length() + 1 == words%5Bi%5D.length() && words%5Bi%5D.startsWith(tmp)) %7B%0A                    tmp = words%5Bi%5D;%0A                %7D%0A            %7D%0A        %7D%0A        result.add(tmp);%0A        result.sort((a, b) -%3E %7B%0A            if (a.length() %3C b.length()) %7B%0A                return 1;%0A            %7D else if (a.length() %3E b.length()) %7B%0A
+for (String word : words) %7B%0A            boolean found = true;%0A            String tmp = %22%22;%0A            for (int i = 0; i %3C word.length(); i++) %7B%0A                tmp += word.charAt(i);%0A                if (!set.contains(tmp)) %7B%0A                    found = false;%0A                    break;%0A          
      
+ %7D%0A
     
@@ -893,18 +893,10 @@
     
-return -1;
+ %7D
 %0A   
@@ -908,14 +908,18 @@
     
-%7D else
+if (found)
  %7B%0A 
@@ -936,38 +936,28 @@
      return 
-a.compareTo(b)
+word
 ;%0A          
@@ -961,34 +961,32 @@
      %7D%0A        %7D
-);
 %0A        return 
@@ -989,21 +989,10 @@
 urn 
-result.get(0)
+%22%22
 ;%0A  
@@ -1085,18 +1085,16 @@
 m720();%0A
-//
         
@@ -1186,18 +1186,16 @@
 / world%0A
-//
         
@@ -1309,18 +1309,16 @@
 / apple%0A
-//
         
@@ -1371,34 +1371,32 @@
 %5B%5D%7B%22a%22%7D)); // a%0A
-//
         System.o
@@ -1454,18 +1454,16 @@
 ); // a%0A
-//
         
@@ -1611,18 +1611,16 @@
 / latte%0A
-//
         
@@ -1778,18 +1778,16 @@
  // eyj%0A
-//
         

Update problem 720