Number Of Occurences Of A Word In A Sentence

INPUT: A sentence containing one or many words like "Hello World Hello Java". We assume that no punctuation marks have been used.

OUTPUT: The number of occurenes of each word. For example, in the above example, the output we get is:
Hello - 2
World - 1
Java - 1
Note that the words "Hello" and "hello" are not the same i.e. the words are case-sensitive

BRUTE FORCE METHOD:
The first step is to break the sentence into words. We then store the words in an ArrayList for ease.

The brute force method is obviously to compare every word in the sentence with every other word. This will take ϴ(n²) for a n-worded sentence as it will involve 2 nested for-loops and every possible pair will be checked.

HASH-MAP IMPLEMENTATION:
In this approach, the first step remains the same - to break the sentence up ino words and arrange the in an ArrayList. Note that this step costs ϴ(n) as 1 full traversal of the array is needed.

However, we now count the number of occurences using Hash-Map instead. We create a HashMap named "map" which has the ASCII value of each word as its key and the word itself as its value. We then iterate over this HashMap and print count of each word. To store count, we either implement another HashMap or a set of variables.

Note that the above step finds the number of occurences in O(n) time. The worst case will be achieved when each word is distinct in the sentence. Thus, at the cost of O(n) extra memory, we reduced the ime-complexity of the programme from ϴ(n²) to O(n).