![]() The keying into the map will be case sensitive, which will create a problem. Below I have shown a sample map after we have inserted all the above words and also the word “hello’. In similar way other words are added to the map. Now we encounter “pots”, and key into the location using the sorted pattern “opst” and fetch the existing linked list and add this word “pots” at the head. Because it is the first string, there is no associated linked list in the map, so we allocate it and add the word “opts”. Say if we encounter “opts” first, then we key into the map using “opst” and fetch the linked list. ![]() The sorted pattern is “opst”, using this string as a key into the map we land in the same location for each of these strings. In short, the character sorted pattern of the words are used to key in the map and then the actual word is added into the linked list in that location of the map.įor example the words “spot”, “post”, “pots”, “opst” are jumble words, that is, they have the same sorted character patterns. Each value in the map is a pointer to list, which will hold the list meaningful words having the same sorted pattern. Therefore if we take a set of jumble words and then sort the characters of each of them, and use the sorted pattern as the key in the map, it will land in the same location (collision) of the map. This time I will use a map or a hashmap with chains.Ī set of meaningful words whose characters are permutations of each other (referred to as jumble words from now on) will have a unique pattern when sorted (either non-increasing or non-decreasing). The implementation I made with C used trie trees to search (at that time I did not know what I constructed already had a name). Recently I am learning Perl and brushing up C++, therefore I will post jumble word solver written in C++ and Perl in this post.įirst, let us review the theory. I will update the post with this (hope to update!) with the new changes, but before it I would like to post the the same stuff in other languages and with different datastructure. I have already posted a jumbled word solver written in C language, although what I posted is actually become old, as I have changed some of the things in the code.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |