/
Main.java
124 lines (105 loc) · 3.21 KB
/
Main.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
package com.foo.pkg;
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.TreeMap;
public class Main {
/* index to keep words sorted by length */
TreeMap<Integer,ArrayList<String>> map;
/* index to keep words sorted alphabetically */
Trie trie;
public Main(){
map = new TreeMap<Integer, ArrayList<String>>();
trie = new Trie();
}
/*
* This method creates both indexes by calling
* insertWord() and buildMap()
*/
public void buildTrie(String word){
//for(String word : words){
trie.insertWord(word);
buildMap(word);
//}
}
/*
* This method groups words of same length into an ArrayList
* and indexes these lists by their length
*/
public void buildMap(String word){
int key = word.length();
ArrayList<String> wordList = map.get(key);
if(wordList == null){
wordList = new ArrayList<String>();
wordList.add(word);
map.put(key, wordList);
}
else{
wordList.add(word);
}
}
/*
* This method recursively checks the presence of compound words
* in the list
*/
public boolean isCompoundWord(String word,boolean isAtomicWord){
// to filter atomic words
if(trie.containsWord(word) && isAtomicWord == false)
return true;
for(int i=0;i<word.length();i++){
String firstPart = word.substring(0, i);
String lastPart = word.substring(i);
if(trie.containsWord(firstPart) && isCompoundWord(lastPart, false)){
return true;
}
}
return false;
}
/*
* This method gets the list of words from the map index
* then it checks to see if they are compound
* It also keeps a counter to count all such words in the list
*/
public void findLongestWord() throws IOException{
Iterator<Integer> keySetIter = map.descendingKeySet().iterator();
ArrayList<String> wordList;
int countNumOfCompoundWords = 0;
//String fileName = "/home/subhendu/Desktop/result.txt";
//BufferedWriter bw = new BufferedWriter(new FileWriter(fileName));
while(keySetIter.hasNext()){
wordList = map.get(keySetIter.next());
for(String word : wordList){
if(isCompoundWord(word,true)){
countNumOfCompoundWords++;
//bw.write(word);
//bw.newLine();
//if(countNumOfCompoundWords < 3)
//prints only first two longest compound words
//System.out.println(word);
}
}
}
//bw.flush();bw.close();
System.out.println("Total number of compound words: " + countNumOfCompoundWords);
}
public static void main(String[] args) throws IOException {
Main obj = new Main();
String path = "wordsforproblem.txt";
BufferedReader br = new BufferedReader(new FileReader(path));
String word;
//long start = System.currentTimeMillis();
//read the file one line at a time and build both indexes
while((word = br.readLine())!=null){
obj.buildTrie(word);
}
br.close();
long start = System.currentTimeMillis();
obj.findLongestWord();
long stop = System.currentTimeMillis();
System.out.println("Execution time: " + (stop - start) + " ms");
}
}