What is an appropriate data structure?

Hi,

I am working on a program that accepts a string of 7 letters and then tries to find every word in a dictionary that contains those 7 letters.

Basically it is an anagram program that finds valid scrabble words with given letters.

Anyway, my dictionary file is a word list of over 200,000 words stored in a text file. My queston is, should i find all possible letter combinations of my 7 letters then compare each combination against each word in the list then return all matches?

I'm not to concerned with the algorithm at present as it will evolve as i go, but i am trying to figure out the best way to store the word list.

Should i just keep them in a file or should i try load them into an array or some other kind of structure? I did try loading them all into a sql database but people have told me that sql is quite inefficient for what i am trying to do.

Any advice would be great.

Thanks :)

Quote:

---

Anyway, my dictionary file is a word list of over 200,000 words stored in a text file. My queston is, should i find all possible letter combinations of my 7 letters then compare each combination against each word in the list then return all matches?

---

That's a whole lot of CPU cycles. To make things more efficient I would probably use a hash table.

There is a much faster way. Here's an example.

Word list:

Code:

---

alloc
free
locale
main
program

---

Scrabble letters

Code:

---

locamle

---

What do you do? First, sort and enumerate the letters of each word in the word list, and your letter rack itself:

Code:

---

program
1 'a'
0 'b'
0 'c'
...
1 'g'
...
1 'm'
0 'n'
1 'o'
1 'p'
0 'q'
2 'r'
...

---

Then you check if each word can be formed using the given letters in the rack. Figure that out yourself.

Since programmers learn best by example, here's one for you...

Code:

---

#include<stdio.h>
int main( void ) { printf("Programmers learn best by example.\n"); return 0; }

---

You also don't need a ; at the end of your main function...

(Note for posterity: This refers to the above poster's sig.)

Quzah.

Daggnabbit, that hurt. I'm scarred for life :D

You can read the text file word by word, transform it as stated in my post above, check if it can be formed using the tiles, keep/discard and read the next one in. That way, you won't be using much RAM at all. That is, if memory is an issue. If it isn't, I have ways to speed things up :cool: