[20.7] find the longest word made of other words

1. Example

Sort By Length + LeetCode: Word Break 


Input from file :

"This" "is" "example" "an" "anexample" "Thisisanexample" "Thisistheexample"

Output :

"Thisisanexample" from "This" "is" "anexample" or "This" "is"  "an" "example"

2. Implementation
1.O(n log n) Sort the array by size, putting the longest word at the front
2.O(d) For each word, split it in all possible ways.
That is, for "test", split it into
{"t","est"}
{"te","st"}
{"tes","t"}
3.O(1) Then , for each pairing, check if the first half and the second both exist elsewhere in the array.
4. "Short circut" by returning the first string we find that fit condition #3
Time :O(n log n + n * d), Space:O(n) hashtable to find if the split string in array

1.O(n log n) Sort the array in alphabetical order
2.O( log n) Rather than looking up the word in a hash table, we would use binary search in the array
3. We would no longer be able to short circuit

import java.util.Arrays;
import java.util.Comparator;
import java.util.HashSet;
public class HelloWorld{



//    Given a list of words, write a program to find the longest word made of other
//    words in the list.
//    EXAMPLE
//    Input: cat, banana, dog, nana, walk, walker, dogwalker
//    Output: dogwalker

    static String findLongestWord(String[] words) {
        if (words == null || words.length == 0) return null;
        HashSet map = new HashSet();
        for (String word : words) {
            map.add(word);
        }
        Arrays.sort(words, new Comparator() {
            @Override
            public int compare(String o1, String o2) {
                return ((Integer) o2.length()).compareTo(o1.length());
            }
        });
        for (String word : words) {
            if (isBreakable(word, map)) {
                return word;
            }
        }
        return "";
    }
    private static boolean isBreakable(String word, HashSet set){
        boolean[] res = new boolean[word.length()+1];
        res[0] = true;
        for (int i = 0 ; i < word.length();i++){
            StringBuilder str = new StringBuilder( word.substring(0,i+1) );
            for (int j=0;j <= i;j++){
                if (res[j] && set.contains(str.toString())){
                    res[i+1] = true;
                    break;
                }
                str.deleteCharAt(0);
            }
        }
        return res[word.length()];
    }
//
//    private static boolean isValid(String word, boolean isOriginal, //XXX: check originality!
//            HashSet map) {
//        if (!isOriginal && map.contains(word)) 
//           return true;
//        for (int i = 1; i < word.length(); ++i) {
//            String left = word.substring(0, i);
//            String right = word.substring(i);
//            if (isValid(left, false, map) && isValid(right, false, map))
//                return true;
//        }
//        return false;
//    }
//
    
    public static void main(String[]args) {
        String[]a= {"cat", "banana", "dog", "nana", "walk", "runner", "dogrunners", "s"};
        System.out.println(findLongestWord(a));
    }

}

// 1. Sort the array of string by length
class LengthComparator implements Comparator
{
      @Override
      public int compare (String s1 ,String s2)
      {
           if ( s1.length() > s2.length() ) return -1;
           if ( s1.length() < s2.length() ) return 1;
           return 0;
      }
}

public static void main (String[] args)
{
      BufferedReader br = null;
      try
      {




           // 1. Store the word from the file
           File file = new File(args[0]);
           br = new BufferedReader( new InputStreamReader(new FileInputStream(file)));
           Strign line = null;
           String[ ]words = new String[]{};
           while ( line=br.readLine() != null  )
                words = line.split("\\s+"); // splitting the string with spaces
             





           // 2. O(n log n) Sort the array by size, putting the longest word at the front

           Arrays.sort(  words, new LengthComparator() );





           // 3. O(1) Then , for each pairing, check if the first half and the second both exist elsewhere in the array.

           for (String str: words)
           {





                if ( str! =null )
                {
                String current = new String(str);
                for (String str2: words)
                {
                      // Note : not the same and str2 is a part of str
                      //        remove that part
                      if (  !str2.equals(current) && str.contains(str2) )
                            str = str.repalce(str2, "");
                }

                if ( str.length() == 0 )
                {
                      System.out.println(current);
                      break;
                }
                }







           }



         
      }
      catch(FileNotFoundException e)
      {
           System.out.println("File Not Found");
           return;
      }
      catch (IOException e)
      {
           e.printStackTrace();
      }
      finally
      {
           try
           {
                if (br != null)
                  br.close();
           }
           catch( IOException e)
           {
                e.printStackTrace();
           }
      }
}
// 2. Sort the array in alphabetical order
Arrays.sort( words );

3. similar Ones
http://stackoverflow.com/questions/29482947/substring-manipulation-in-java-find-the-longest-word-made-from-the-other-words http://stackoverflow.com/questions/29482947/substring-manipulation-in-java-find-the-longest-word-made-from-the-other-words