Matching words with same letters

Question

I am trying to match two words and then print them out e.g 'act' and 'cat' have 'a,'c' and 't' in them so they match. here is my code:

#include <stdio.h>
#include <stdlib.h>

main()
{
  FILE        *fptr;
  char        words[100], input[100], store[1000][100] 
  char        ch
  int         i,j,k,z,b,*ptr;

  ptr = &b;

  fptr = fopen("d:\\words.txt","r");
  if (fptr == NULL)
  {
           printf("Could not open file");
           exit(1);
  }

  printf("Enter the scrambled word: ");
  fflush(stdin);
  fgets (input,sizeof(input),stdin);

  i = 0;
  while (fgets(words,sizeof(words),fptr) != NULL)
  {     
        if (strlen(input) == strlen(words))
        {
           strcpy(store[i],words);
           ++i;
        }
  }
  //this is where the problem is:
  /*am trying to match the letters in two words, if they don't match then store 1 in b,
  if b=0 then print out the word which matched with string 'input'*/
  for(z = 0; z < 1000; ++z)
  {
        b = 0;
        for(j = 0; j < strlen(input); ++j)
        {
              for(k = 0; k < strlen(store[z]); ++k)
              {
                    if(input[j] != store[z][k])
                        *ptr = 1;          
              }
        }
        if(*ptr == 0)
        {          
                   printf("Word #%2d is: %s\n", z, store[z]);   
        }
  }



  fflush(stdin);
  getchar();
}

Please I really need help. Am sorry if I haven't made my question clear.

You say in your code "this is where the problem is" but you don't tell us what the issue is that your having and how it differs from what you expect. — Kevin Kunderman, Aug 22 '13 at 12:34

score 5 · Answer 1 · edited May 23 '17 at 12:28

5

Sorting the letters in both strings and then comparing them is one of the simpler ways of doing what you require. (assuming you are familiar with sorting)

It may not be the most efficient but I then again, worrying too much about efficiency is usually best left until after you have a working solution and performance metrics.

If you want some more efficient methods to detect if two words are anagrams, check out the link provided by Mats Petersson, Optimizing very often used anagram function

edited May 23 '17 at 12:28

Community

1
1

answered Aug 22 '13 at 12:33

Colin D

5,641
1
23
35

5

It has been found in the question/answer linked below that sorting is not the most efficient way. But yes, it is a workable method. http://stackoverflow.com/questions/18123959/optimizing-very-often-used-anagram-function/18124989#18124989 – Mats Petersson Aug 22 '13 at 12:37
Totally agree with Mats Petersson. Prefer the implementation with voting arrays in case of repetitive calls to this procedure, complexity is linear with length of strings and with the size of the alphabet. – Bentoy13 Aug 22 '13 at 12:48

score 0 · Answer 2 · answered Aug 22 '13 at 13:17

Something like this could also work.. (sorry ugly reading code, very busy with something else)...

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <Windows.h>

#include <string>
#include <list>
#include <map>
#include <sstream>
#include <algorithm>

using namespace std;

map< string, list<string> > items;
int c = 0;

void readFile() {
        FILE * f = fopen( "c:\\t\\words.txt", "r" );
        fseek(f, 0L, SEEK_END);
        int size = ftell(f);
        fseek(f, 0L, SEEK_SET);
        char * data = (char*)malloc(size);
        fread(data, size, 1, f);

        string s = string(data);
        istringstream reader(s);
        while(reader) {
            string sub;
            reader >> sub;

            string original = sub;
            sort( sub.begin(), sub.end() );

            items[sub].push_back(original);        
            c++;
        }


        free(data);
        fclose(f);
}

bool     check( const string & v ) {
    string requestStr = v;
    sort( requestStr.begin(), requestStr.end() );
    printf("Requested: %s [%s]\n", v.c_str(), requestStr.c_str());

    if (items.find(requestStr) == items.end()) {
        printf("Not found\n");
        return false;
    }

    list<string>::iterator it = items[requestStr].begin();

    while (it != items[requestStr].end()) {
        printf("Found: %s\n", (*it).c_str());       
        it++;
    }
}

int main(int argc, char ** argv) {
    long t1 = GetTickCount();
    readFile();
    printf("Read wordlist (%i): %li ms\n", c, GetTickCount() - t1 );

    string str = "holiday";
     t1 = GetTickCount();
    check(str);
    printf("Time: %li ms\n",  GetTickCount() - t1 );


    str = "tac";
     t1 = GetTickCount();
    check(str);
    printf("Time: %li ms\n",  GetTickCount() - t1 );

    str = "dfgegs";
     t1 = GetTickCount();
    check(str);
    printf("Time: %li ms\n",  GetTickCount() - t1 );

}

results on 109000 words file

Read wordlist (109583): 5969 ms
Requested: holiday [adhiloy]
Found: holiday
Time: 0 ms
Requested: tac [act]
Found: act
Found: cat
Time: 0 ms
Requested: dfgegs [defggs]
Not found
Time: 0 ms

120000 searches takes 7188ms, so around 0.0599ms per search...

Is this c language? If so, I am just a beginner, sorry didn't get it. — Harith, Aug 22 '13 at 13:25
it's с++, not perfect, but gives an idea, so you read all words, sort letters in words and store sorted words in array, actually in the map.. because you will have duplicates each 'value' in the map array itself, it contains all words which looks the same after sorting.. so after that you only need to get a word, also sort letters and look using binary search if your map contains key like that and print results — evilruff, Aug 22 '13 at 13:31
you can remove , its just for GetTickCount() function to do basic measurments — evilruff, Aug 22 '13 at 13:32
I am using c, and I don't think there is something like 'map' — Harith, Aug 22 '13 at 14:46
well, whatever language you are up to, i just proposed an idea, you can write similar code in C, it's just takes a bit more time... — evilruff, Aug 22 '13 at 14:58

Matching words with same letters

2 Answers2