CODEWITHSUNDEEP
iosarraysstringdictionary
Gil Sand
Gil Sand

Reputation: 6040

ios : Find a word in a (huge) dictionary/array

I'm trying to solve a problem that I haven't built yet, so I might be taking this the wrong way. I'm open to other possibilities if you happen to know one.

So, I'd like to simply check if a string exactly exists in a pre-made list of strings. This list could be an array or a dictionary, I'm not sure what's best.

What I'm trying to do is find a fast/optimal way to browse that array and find if my word is in there or not. I was thinking of dichotomic search but I'm not sure about it.

I had two "solutions" :

Solution 1 :

That array/dictionary will contain about 70.000 words, sorted alphabetically. I browse the array from start to end until I reach my match.

This will probably be stupidly slow, specifically if my word starts with a Z.

Solution 2 :

I have an array allTheWords that contains 27 arrays "A", "B", "C", and so on. Each array contains every word starting with that letter.

I check the first letter of my given string, and go browse my array from start to end until I reach my match. That would be drastically faster than solution 1 so, I feel like I'm one step ahead but that it's still non optimal.

Is this viable? Do you know something better? Am I on the right path?

Note : I have zero code about this, I'm still on the paper/theoretical side of the app here, only pseudo code and little drawings.

Upvotes: 0

Views: 321

Answers (1)

Fogmeister
Fogmeister

Reputation: 77621

EDIT

In fact, you could probably just use an NSSet. I believe it uses a similar search to NSDictionary to keep the uniqueness. So you could just use the method [wordSet containsObject:theSearchWord];.

This should (but I can't find the documentation) also give a O(1) search performance and doesn't have the redundancy of the "value" in the dictionary.

Original answer

Hmm... if you use an NSDictionary like this...

{
    <THE WORD>: <BOOL>
}

i.e.

@{
    @"Apple": @YES,
    @"Banana": @YES,
    @"Orange": @YES
}

Then you can do something like this...

NSNumber *wordValue = wordDictionary[@"Apple"];

Then wordValue will either be @YES or nil.

The search times for this is O(1).

If you want to list the words you can use the class method...

[wordDictionary enumerateObjectsAndKeys...

Or you can get an NSArray of the words...

NSArray *justTheWords = [wordDictionary allKeys];

Upvotes: 1

Related Questions