290. Word Pattern | LeetCode Easy | Python Solution | String, Hash Table, Dictionary

Pubblicato il: 02 gennaio 2023
sul canale di: Shaheer Keerirakath

352

Leetcode easy problem 290. Word Pattern, detailed explanation and solution in python language.

LeetCode Problem Link: https://leetcode.com/problems/word-pa...
Solution (Python Code): https://github.com/shaheershukur/Leet...

#leetcode #python #solution

Problem Statement:
Given a pattern and a string s, find if s follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in s.
______________________________________________________________

LeetCode problem solving helps in improving one's problem solving and coding skills . Also, it helps in clearing technical interviews at top tech companies like Microsoft, Google, Amazon, Facebook, Walmart, Apple etc.
(FAANGM, MAANGM, Product based companies)

CC of video:
we are given two strings, pattern and s.
we need to find out whether they both follow the same pattern, or there is bijection between the given two strings.

for example, if we are given pattern="abba", and s="dog cat cat dog",
then we can see here that, the first and last characters in pattern are same,
similarly, the first and last words in s are same.

again, the second and third characters in pattern are same,
similarly, the second and third words in s are same.

so, we can see here that they both follows the same pattern.

now, in case the string s was "dog cat pcat dog", then we can see that the two strings pattern and s does not follow the same pattern.

to find out whether the two strings follow the same pattern, what we can do is, create a unique signature for both the strings, and check whether the two signatures are equal or not.

for example, lets first take the string pattern.
here, for each character in the string, we will assign the index at which the character first occured.
a occured first at index 0. so we will assign 0 here.
b occured first at index 1. so we will assign 1 here.
again, since b occured first at index 1, we will assign 1 here.
since a occured first at index 0, we will assign 0 here.
therefore, this is the signature we have generated for the string pattern.

now, for the string s, for each word in the space seperated string, we will assign the index at which the word first occured.
dog occured first at index 0. so we will assign 0 here.
cat occured first at index 1. so we will assign 1 here.
again, since cat occured first at index 1, we will assign 1 here.
since dog occured first at index 0, we will assign 0 here.
therefore, this is the signature we have generated for the string s.

now we will check whether the signatures we have generated are equal or not.
if they are equal, we will return true.
if they are not equal, we will return false.

now lets code the solution.

we will create a dictionary for storing the first index of characters present in the string pattern.
we are using dictionary so that we can access the value at constant time.

we will create an array for storing the signature for the string pattern.

now we will loop through each character in the string pattern using a for loop.

if the current character is not already present in the index dictionary, that means we are encountering it for the first time. so we will store the current index to the index dictionary.

and also, during each loop, for the current character, we must add the first occurance index to the signature.

now, similarly, we will create an index dictionary and signature array for the string s.

for each word in the space seperated words in the string, we will store the first occurance index in the index dictionary and also, add the first occurance index of each word to the signature array.

at last, we will be checking whether the two signatures are same and returning the result.

In questa pagina del sito puoi guardare il video online 290. Word Pattern | LeetCode Easy | Python Solution | String, Hash Table, Dictionary della durata di ore minuti seconda in buona qualità , che l'utente ha caricato Shaheer Keerirakath 02 gennaio 2023, condividi il link con amici e conoscenti, su youtube questo video è già stato visto 352 volte e gli è piaciuto 4 spettatori. Buona visione!