[No Audio]
In this section, we will be looking at some
practical and real life applications, and
problem solving using Rust. The idea is to
have some hands on experience in real life
problem solving using simple as well as
complicated data types such as Linked lists,
Trees, HashMaps, HashSet, and binary search trees.
The first application we will
implement is that of correct search results
through word grouping. Consider an online
store, the store has many items to sell,
which are searchable. They want to implement
a functionality that, if a user misspelled a
word, they are still being displayed the
correct search results. The business
considers this function to be important from
the user satisfaction and usability
perspectives. The solution to this will
include to first split the words describing
the items that are present in the store into
sets, so that all words in a set are
anagrams. Anagrams are words having exactly
the same letters. The assumption in this
problem is that, the misspelled word will most
probably contain the same letters as in the
original word, but in different order. Let us
start looking at the implementation details.
We will assume that we are given a list of
words describing some items, and we will need
to group the words that are anagrams of each other.
We will be using HashMaps and Loops to
implement this problem. I will first declare
a vector of strings containing some words
have incorrect and incorrect spellings.
[No Audio]
Next, we will implement the
required functionality using a
function. I will name the function as
word_grouping.
[No Audio]
The input to the function
will be the vector of strings
containing the words, and the output will be
grouping of words. So we will need a vector
which will contain string of factors as elements.
[No Audio]
First, I will create an empty HashMap.
[No Audio]
The key part of this HashMap will
be the frequencies of the letters in the word,
and the value part will contain all the words
having the same frequencies of letters. This
way, all the words corresponding to the same
key will be anagrams, and are effectively
stored together inside a HashMap. To compute
the frequencies, we will first create a
vector containing 26 entries, all initialized from 0.
[No Audio]
Each entry will correspond to one letter.
Next, we will iterate through all the
words in the input word list.
[No Audio]
For each word, we will compute
the frequency and the
frequencies of individual characters, so we
will add another loop for iterating through
all the characters in a given word.
[No Audio]
The lower_case function will convert to
lowercase and the .char function will
grab the individual characters from the
current_word. Next, I will update the
frequencies for the current character.
[No Audio]
The c as u32 will essentially grade the ASCII
corresponding to the current character,
and then we will subtract it from the ASCII
corresponding to letter a, and then we'll use
it as an index to update the frequency of the
corresponding letter. For instance, if the
current letter or character is, let's say d,
the ASCII for d is 100. We will subtract it
from the ASCII of letter a which is 97, so we
will have a value of 3. This means that
for the index of 3, we will have its value
incremented by a value of 1. Please note
again that indexes in Rust starts from 0,
and therefore the index for d will be 3.
Now once the inner loop is over, we will have
the frequencies of all the letters in the
word stored in the array of char_freq.
We will use this array as the key to
insert the corresponding word in the HashMap.
To use it as a single entry for the key part,
I have converted into string using iterators.
[No Audio]
The map function will convert each char to
string. Next we use the collect function to
have the result in a string format. The key
variable now contains the frequencies of the
characters in the string format. The key
variable will now be used as a key for the
hash, and we will insert the current_word
into it as a value. The
current_word is the word from the word_list,
that is under processing in
the current iteration of the loop.
[No Audio]
We use the .or_insert function,
which will ensure that if there is no already
existing entry for the value part, so by
default, an empty vector will be inserted.
And then we push the current_word
for the value part. If more than two words
have the frequency of characters, then
they will correspond to the same key in the
HashMap. In fact, they will correspond to the
value part of the HashMap corresponding to
the same key. Next, we will make sure that
before processing the next word in the word_list
in the next iteration of the loop,
we re initialize the char_freq
variable from all zeros. This is
important, because we do not want to use the
values or frequencies of characters stored
for the previous word.
[No Audio]
Outside the loop, I
will display the HashMap using a loop. Let us
add the code and a suitable print
statement for this purpose.
[No Audio]
Finally, I will return the grouping of the
words in a string vector. You may note that
the individual groups are basically the
entries corresponding to the same keys in the
HashMap, since they have the same frequencies
of characters. To return the grouping, I will
just return the value part corresponding to
keys, I will use iterators again for this purpose.
[No Audio]
I will use the map function to
transform the HashMap entries from
key,value format to only value format. This is
because, I am only interested in the value
part, which contains the individual groups.
First I will mention the inputs. The first
input corresponds to the keys, which I will
ignore by using underscore. The second one is
the value part, which contains the groups of
words corresponding to the same key. This is
the part which I am interested in. For the
returning or transformation or mapping part,
I will just mention v. This will now take
each and every entry of the HashMap, and will
return only the value part. Finally, I will
use the collect function to have all the
information in a single collection. This
statement will be the returning value.
I will use this function now in the main. I
will call the function and we'll store the
result in a variable.
[No Audio]
Now let us assume that
the user writes some word in the search bar.
I would like to return the group that query
word belongs to. Let us first declare a
variable which will store the user entered word.
[No Audio]
Next, I will iterate through all the
groups to see the groups to which the word belongs.
[No Audio]
They can contents function
can be used to check if the input word is
contained within the group.
[No Audio]
I'm allowed a suitable print statement in this case.
[No Audio]
Okay, it's time to see the action.
Let me execute the code.
[No Audio]
First, we have the HashMap being
displayed showing its keys and the
corresponding values. The keys are strings of
zeros and ones reflecting the frequencies of
the characters, and the values are the words
that are anagrams of each other. Finally, for
the input word, we have the corresponding group.
We end this tutorial here, I hope you
would have enjoyed problem solving using
HashMap and loops. Do come back again for
more and until next tutorial, happy Rust programming.
[No Audio]