Skip to main content
TRICK TO REDUCE TIME COMPLEXITY USING HASH CONCEPT [DICTIONARY]


Today, I learned a new way to know the indices of characters in a string. 

Example:

If you have a string containing alphabets, and while doing some problem, inside a for loop, you need to access a particular alphabet's index in that string, you will definitely use string.index(k) function, where 'k' represents alphabet. But, it takes O(N) time, as it searches the whole string and returns the index as soon as it finds that particular alphabet. As we are performing this operation inside another for loop, this logic takes O(N^2) for implementation. But, we can know the index of that particular alphabet in O(1) time. Let us see HOW?




Here, in the above code, we use the dictionary to store the alphabets in a string as keys and the corresponding indices as values. As the dictionary uses the hash table concept for accessing the value of a particular key, it takes a constant time,  i.e., O(1). 

So, now if we use this trick, then our search becomes faster and efficient. 

Comment if you find anything wrong in this post. Thank you.




Labels:

Comments

Post a Comment

Popular posts from this blog

CHATBOT WITH SPEECH RECOGNITION AND PYTTSX3 USING PYTHON

NOTE: VIEW THIS POST IN DESKTOP SITE FOR THE BEST EXPERIENCE Hello guys. Welcome to my blog. Here I will explain to you how to create a chatbot that has speech as it’s both input and also output. So, let us get started. In this tutorial, I am using some of the libraries in Python like SpeechRecognition, Pyaudio, Chatterbot et cetera. I am going to explain to you how to install these libraries and work with them one by one separately and at last how to integrate them. SPEECH TO TEXT At first, you have to install the Speech Recognition library. You should not use the Python3.7 version because it does not support speech recognition. I am using a 3.6 version for this tutorial. Now, you should install the speech recognition library from the command prompt. Use the following command. pip3.6 install SpeechRecognition Now, you should install PyAudio. First, you have to find the version of your Python and also the configuration of your machine. Open your cmd and type p...
3 comments
Read more

LENGTH OF LONGEST VALID SUBSTRING

GIVEN A STRING OF PARENTHESIS, PRINT THE LENGTH OF THE LONGEST BALANCED SUBSTRING . FOR EXAMPLE: GIVEN,                1.  ()() ---> 4                 2.  ()())()()() ---> 6  Brute Force Approach:   It is to find all the substrings, and check whether they are balanced or not, and simultaneously updating the result if we find a larger valid substring than the previous one. But, this takes the time of O(N^3), since finding all the substrings take O(N^2), and for each substring, to find whether it is a valid substring, it takes a time of O(N), so this constitutes a total of O(N^3).  USING STACK:  In this approach, we will maintain a stack to store the indices of the traversed opening brackets i.e., '('. [YOU WILL KNOW THE REASON SOON, KEEP READING THE POST].  And a variable res , to store the length of the longest substring known till now....
1 comment
Read more

RECOGNITION OF HANDWRITTEN DIGITS(MNIST DATA) PART ONE USING PYTORCH

HELLO GUYS, IN THIS BLOG POST I WANT TO SHOW THE BASIC INTRO TO IDENTIFICATION OF HANDWRITTEN DIGITS USING PYTORCH MNIST DATA. MNIST DATA IS THE COLLECTION OF HANDWRITTEN DIGITS. MNIST CONTAINS 70,000 HANDWRITTEN DIGITS, 60,000 FOR TRAINING AND REMAINING 10,000 ARE FOR TESTING.  THE  IMAGES ARE GRAYSCALE AND 28x28 PIXELS. WE CAN DOWNLOAD THE DATASET USING THE CODE BELOW. Here, the parameters batch_size is kept to 64 so that the training images are grouped into 64 each and shuffle is kept to TRUE, such that each time we run the code it shuffles the data and returns an iterable with new groups of batch_size. As the trainloader is iterable, we are iterating through it and collecting the first batch of images and it's corresponding labels into images and labels respectively. Now, run the above code and see the output. you will see something like this. torch.Size([64, 1, 28, 28]) torch.Size([64])  It shows that there are 64 images with grayscale an...
Post a Comment
Read more