I have seen similar problems on chegg; however, I need all of the code to stay e
ID: 3551254 • Letter: I
Question
I have seen similar problems on chegg; however, I need all of the code to stay exactly the same except for where I've indicated add code.
Write a Java program that reads a large file of strings and determines whether all the strings are unique.You should use an ArrayList container to hold your strings for comparison purposes to determine uniqueness. You are free to use whatever algorithm you can devise to solve this problem but be aware that if you use a brute-force algorithm your program will take a very long time - even on the smaller file. The most obvious brute force approach would be to search the ArrayList for the presence of each new string before you put it into the ArrayList. Each search requires O(n) comparisons if there are n elements in the Array at that time. There are N total searches to be done. Thus the total number of comparisons needed for this brute force approach is n * N where n is the number of elements in the ArrayList at any given time and N is the total number of strings that get read in. Since little n varies from 0 to N you have a total number 1+2+3+4+5+6+ ... + N comparisons. This sum is (N squared + N)/2. Considering that even the little file has 10,000 strings in it, your brute force approach requires millions of comparisons. The larger test file has 3 million strings in it. A brute force algorithm would require millions * millions of comparisons. A brute force approach is just not feasible for this problem.
Explanation / Answer
import java.util.*;
import java.io.*;
public class Lab6
{
public static void main( String args[] ) throws Exception
{
ArrayList<String> list = new ArrayList<String>();
BufferedReader infile = new BufferedReader( new FileReader( args[0] ) );
long startTime = System.currentTimeMillis();
while (infile.ready())
list.add( infile.readLine() );
infile.close();
System.out.printf( "List contains %d Strings. ",list.size());
boolean hasDupe = false;
String dupe="";
HashSet<String> hs = new HashSet<String>();
for (String s : list) {
if(hs.contains(s)){
hasDupe = true;
dupe=s;
break;
} else {
hs.add(s);
}
}
if (hasDupe)
System.out.println("List contains dupe: " + dupe );
else
System.out.println("List contains NO dupes.");
long endTime = System.currentTimeMillis();
long ms = endTime-startTime;
System.out.printf("Elapsed time: %f seconds ", ms/1000.0);
}
}