Arranging words in sentences alphabetically

Question

For an online contest whose problem is here, I wrote some code.

In this problem the input will consist of a number of lines of English text consisting of the letters of the English alphabet, the punctuation marks ' (apostrophe), . (full stop), , (comma), ; (semicolon), : (colon) and white space characters (blank, newline).
Your task is print the words in the text in lexicographic order (that is, dictionary order). Each word should appear exactly once in your list. You can ignore the case (for instance, "The" and "the" are to be treated as the same word.) There should be no uppercase letters in the output.

For example, consider the following candidate for the input text:

This is a sample piece of text to illustrate this 
problem.

The corresponding output would read as:

a
illustrate
is
of
piece
problem
sample
text
this
to

Input format

The first line of input contains a single integer \$N\$, indicating the number of lines in the input. This is followed by \$N\$ lines of input text.

Output format

The first line of output contains a single integer \$M\$ indicating the number of distinct words in the given text. The next \$M\$ lines list out these words in lexicographic order.

Test data

You may assume that \$N ≤ 10000\$ and that there are at most 80 characters in each line. You may also assume that there are at the most 1000 distinct words in the given text.

Example

We now illustrate the input and output formats using the above example.

Sample input

2
This is a sample piece of text to illustrate this 
problem. 

Sample output

10
a
illustrate
is
of
piece
problem
sample
text
this
to

It is working perfectly as far as I know. When I run my code, it passes all tests.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/**
 * Created by aditya on 14-10-2014.
 */
public class Main {

    public static void main(String args[]) {

        Scanner scan = new Scanner(System.in);
        int n = Integer.parseInt(scan.nextLine());
        ArrayList<String> lines = new ArrayList<String>();
        ArrayList<String> words = new ArrayList<String>();
        ArrayList<String> words_2 = new ArrayList<String>();
        boolean once_entered = true;
        for (int i = 0; i < n; i++) {
            lines.add(i, scan.nextLine() + " ");
        }
        for (int i = 0; i < n; i++) {
            String word = "";
            for (int j = 0; j < lines.get(i).length(); j++) {
                char char_0 = lines.get(i).toLowerCase().charAt(j);
                if ((int) (char_0) >= (int) ('a') && (int) (char_0) <= (int) ('z')) {
                    word += char_0;
                    once_entered = false;
                } else if (!once_entered) {
                    words.add(word);
                    word = "";
                    once_entered = true;
                }
            }
        }
        for (int i = 0; i < words.size(); i++) {
            boolean contains =false;
            for(int j=0;j<words_2.size();j++){
                if(words_2.get(j).contentEquals(words.get(i)))
                    contains=true;
            }
            if(!contains)
                words_2.add(words.get(i));
        }
        Collections.sort(words_2);
        System.out.println(words_2.size());
        for (int i = 0; i < words_2.size(); i++) {
            System.out.println(words_2.get(i));
        }
    }
}

Answer 1

Your code here is far more complicated than it needs to be. The trick you need to follow is four-fold:

1. Use your library functionality
2. Use Regular Expressions
3. Use buffered input/output for performance
4. bend the rules on the input side.

You go to great lengths to store the data in two arrays (with bad names words and words_2), and you use the one to check for words in the other. The right structure in Java is a Set, which automatically, and efficiently does the check for you. Further, there's another specialized set, called the TreeSet which stores the data in sorted order already.

Regular Expressions are a good way to identify patterns in the data. They take some getting used to, but, because of the way they can be pre-compiled, and reused, they are fast. Note that the Scanner class looks for regular expressions.

When using input, and output, you get better performance if you use fewer operations. You should wrap the System.in in a BufferedInputStream, and perform all the output to a StringBuilder, and then dump that to System.out in one operation.

Now, about bending the rules on the input side.....

Many programming challenges are set up to work in many languages, including things like C, C++, etc. Some of those languages need to have an idea of how much space to allocate before processing the data. That's why the description says it will contain the number of lines, as well as the maximum line length. If you assume that the input will be valid, then there is no reason to process the data line by line, you can do it word by word, and just forget about the line count in the first line....

How would I do it?

    try (Scanner scan = new Scanner(new BufferedInputStream(System.in));) {
        // find word boundaries...
        scan.useDelimiter(Pattern.compile("[\\s;:,.'\n]+", Pattern.MULTILINE));
        scan.nextLine(); // ignore the count
        Set<String> words = new TreeSet<>();
        while (scan.hasNext()) {
            String word = scan.next().toLowerCase();
            words.add(word);
        }
        StringBuilder sb = new StringBuilder();
        sb.append(words.size()).append("\n");
        for (String word : words) {
            sb.append(word).append("\n");
        }
        System.out.print(sb.toString());
        System.out.flush();
    }

On further reflection, I would split the logic in to two parts, a word-finder, and a word printer:

Set<String> words = parseWords(System.in);
System.out.println(formatWords(words));

Answer 2

From what your task says I cannot specify your input method (Scanner or command line arguments) however your code can be simplified dramatically.

Firstly HashSet is an object that holds unique objects meaning no two strings can match inside therefore you should use:

Set<String> uniquewords = new HashSet<String>();

And add to that for each word.

Secondly you have to remove everything from the input that isn't a alphabet character or space or a newline or apostrophe (Otherwise "When the farmer's wife called Bob back in, the other farmers went back to their work as well." both "farmer's" and "farmers" would be the same string. The simple removal of characters can be achieved with a regex.

[^A-Za-z\s\n] 
^ mean NOT so we are not looking for the following
A-Z and a-z are capital and lowercase characters
\s is a space character
\n is a new line character

This can be used in the replaceall() function on a string via

// \n and \s are escaped
replaceAll("[^A-Za-z\\n\\s']", "")

This will remove everything else from the string then you can toLowerCase() so that "ThIs" will be the same as "this" and then split at the spaces with split(" ") to receive each word.

A TreeSet can be used to store the remaining words whilst keeping the "natural" ordering

My function to complete the uniqueness and sorting of the lines would be

public static Set<String> getUniqueWords(List<String> input) {
    Set<String> uniquewords = new TreeSet<String>();
    for (String s : input) {
        uniquewords.addAll(Arrays.asList(s.replaceAll("[^A-Za-z\\s]", "").toLowerCase().split(" ")));
    }
    return uniquewords;
}

If you wish to only use simpler data types (primitive and ArrayList) then the following will apply

For each word you will have to check if the ArrayList contains your value already since you can place two of the same value into it.

for (String word : words) {
    if (!uniquewords.contains(word)) {
        uniquewords.add(word);
    }
}

When you insert into an ArrayList the "natural" ordering of the types is not accounted for as such the List will not be in alphabetical order but in the order you put the data in. Before you return you will have to call Collections.sort() which will order each string in alphabetical order

My code using only primitive and ArrayList types is as follows (It is a little more spread out):

public static List<String> getUniqueWords(List<String> input) {
    List<String> uniquewords = new ArrayList<String>();
    for (String s : input) {
        String[] words = s.replaceAll("[^A-Za-z\\s]", "").toLowerCase().split(" ");
        for (String word : words) {
            if (!uniquewords.contains(word)) {
                uniquewords.add(word);
            }
        }
    }
    Collections.sort(uniquewords);
    return uniquewords;
}

Answer 3

Useless cast

I think you can rewrite :

if((int) (char_0) >= (int) ('a') && (int) (char_0) <= (int) ('z'))

in a more simple way :

if ('a' <= char_0 && char_0 <= 'z')

Answer 4

When the farmer's wife called Bob back in, the other farmers went back to their work as well.

Your code doesn't provide the correct solution for this.

It splits "farmer's" into "farmer" and "s". That's not correct; it's one word.

To handle this, you should add a special case for the ' character where you currently check if a character is in the range a-z.