Thread: Word Counting Help(newbie)

I would use for loops instead of while, because if you know the number of loops, it is better readable than some ++i and ++pass statements.

And you can think about contain of your data structures. Do you need to store all words? Wouldn't it be better to keep only different words in your list, and maybe number of occurences in input for each word?

The core of your problem is that you are counting the number of pairs of words, not duplicates. The easyest solution is to simply sort the vector. The other problem is the strangeness of your loops.

Code:

for(int i=0;i<size;++i) {
    for(int j=i+1;j<size;++j) {
        all pairs i,j with i<j here..
    }
}

This loop will cover all pairs in much the same way as your loop, it's just simpler and faster. You still need a way to make sure that you only count a duplicate between words[i] == words[j] if and only if there is no words[i-k] == words[i] One way would be to swap every second element of each matching pair with the last element in the vector and remove the last element. This will alter the order of the list, and you might as well sort, the faster, beter solution. You could also have another vetor of bool that you use as a look up table to see if any duplicate has been counted before. Still, sort the vector, or use a set and count duplicates as you read the words in.

Thank you greatly for all of the advice. I have written the following code based simply on aerian's advice, prior to reading the other's. I will go ahead and post it while I ponder the rest.

This is working although I'm sure it is by far the best means to solve the problem. Also it was aerian who got me to think of doing it this way but I seriously doubt it's exactly what he intended. Again thanks for the replies and please keep it coming.

Code:

#include<iostream>
#include<string>
#include<vector>
#include<stdlib.h>

using namespace std;

int main()
{
 // get input
 cout << "Please enter a list a words." << endl;
 vector<string> words;
 string x;
 int count = 0;

 while(cin >> x)
 {
  int duplicate = 0;
  if (count != 0)
     {
      for(int i = 0; i < words.size(); i ++)
        {
         if(x == words[i])
              duplicate = 1;
        }
      if(duplicate == 0)
         words.push_back(x);
     }

  else
      words.push_back(x);
  count++;
 }

 cout << endl << "You have entered " << words.size() << " distinct words.";
 system("pause");
 return 0;
}

Hmm, it seems to be good now. More or less, it's what I intended
At least it is easier to read for me. Though, my knowledge of STL is reduced to it's name and to some intuition, what else can be in such a library, if not some useful templates?

Now, if all is working, you can think about changing the algorithm to something faster. That linear search is rather slow, try your program on huge input (probably 50000 words will be enough).
It will consume about O(n^2) time. (For explanation of that notation, see some issue of Code Journal.)

What about binary search? Maybe it is even implemented in some function/class in the library.
(it will take O(n * log n))

And after you have done that, you can try even more sophisticated algorithms. Try keeping your words in lexicographical tree It will then take only O(n * length), where length is depth of the tree, thus maximal length of the words.