Isomorphic Strings (LeetCode 205) | Full solution using a HashMap | Easy to understand

Подписаться 43 тыс.

Просмотров 33 тыс.

50% 1

To see more videos like this, you can buy me a coffee: www.buymeacoffee.com/studyalg...
Actual problem on LeetCode: leetcode.com/problems/isomorp...
Chapters:
00:00 - Intro
00:41 - Problem Statement and Description
03:37 - Brute Force has limitations
06:03 - Efficient Solution
09:39 - Dry-run of Code
13:01 - Final Thoughts
📚 Links to topics I talk about in the video:
LeetCode Problems: • Leetcode Solutions
Other String Problems: • Strings
Brute Force: • Brute Force algorithms...
📘 A text based explanation is available at: studyalgorithms.com
Code on Github: github.com/nikoo28/java-solut...
Test-cases on Github: github.com/nikoo28/java-solut...
📖 Reference Books:
Starting Learn to Code: amzn.to/36pU0JO
Favorite book to understand algorithms: amzn.to/39w3YLS
Favorite book for data structures: amzn.to/3oAVBTk
Get started for interview preparation: amzn.to/39ysbkJ
🎥 My Recording Gear:
Recording Light: amzn.to/3pAqh8O
Microphone: amzn.to/2MCX7qU
Recording Camera: amzn.to/3alg9Ky
Tablet to sketch and draw: amzn.to/3pM6Bi4
Surface Pen: amzn.to/3pv6tTs
Laptop to edit videos: amzn.to/2LYpMqn
💻 Get Social 💻
Follow on Facebook at: / studyalgos
Follow on Twitter at: / studyalgorithms
Follow on Tumblr at: / studyalgos
Subscribe to RSS feeds: studyalgorithms.com/feed/
Join fan mail: eepurl.com/g9Dadv
#leetcode #programming #interview

Опубликовано:

4 авг 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 56

@jaxsyntax Год назад

Nikhil, you are one of the only people that make these problems simple and easy to understand. I appreciate your efforts very much!

@rishabhjain7651 Год назад

exactly

@user-lk6gr2je5j 10 месяцев назад

Thank you so much for making these problems simple and easy to understand, your explanation is best.

@Maneeshce2007 Год назад

Really like the way of your explanation Nikhil , it encourages to solve DS problems which otherwise feels very frustrating.

@manishbhardwaj4587 2 месяца назад

best teacher, its hard to follow others even if they have same solution as you! Thankyou!!

@vikashkatiyar1225 4 месяца назад

u got a new subscriber , Thanks Nikhil for amazing quality content

@lalanabiridi8358 9 месяцев назад

Hey nikhil i have a small doubt what happenns if we dont create a new variable mapped char but instead directly compare original with replacement i did that and out of 47 ..12 test cases failed

@hoddybhaba6704 Год назад

Great explaination!

@dobermanbruce2397 Год назад

Really Appreciate your efforts

@ashtonronald 4 месяца назад

problem made extremely intuitive, gg!

@bahubali1939 2 месяца назад

Amazing sirr!! We love you..........

@acethoughtless1596 7 месяцев назад

Very nice explanation !! Thank you!!

@nikoo28 6 месяцев назад

Glad it was helpful!

@parthapardhu3319 10 месяцев назад

Wow.. simply good sir

@BACSShaileshShettar 6 месяцев назад

great explanation

@103_debopriyoghosh_cse_by6 2 месяца назад

U are great , no idea why u are undeerrated

@vinayaksharma7134 3 месяца назад

nice explanation

@sohrab6494 Год назад

Your explanations are great and you make them so much easier to understand. Can you also solve '605. Can Place Flowers'?

@nikoo28 Год назад

thank you so much...sure I will add it to my pipeline of upcoming videos.

@just_a_guy6985 5 месяцев назад

u dont need if condition at start in constraints its given that two strings are of same length

@Isagi__000 3 месяца назад

cool stuff.

@Harshu9669 5 месяцев назад

thanx brother

@subee128 7 месяцев назад

Thanks

@hitheshpk6030 Год назад

Understood

@mma-dost 5 месяцев назад

Java have a method to check the containsValue in the map, but cpp don't have that what should we do like creating another set for storing the values and then like check if the value contains in that something like this? This solved it but what about space complexity using map and set both.

@nikoo28 5 месяцев назад

If you use std::unordered_map, which is implemented as a hash table, the average case time complexity for insertion, deletion, and search is O(1).

@mma-dost 5 месяцев назад

thanks, bhaiya got it@@nikoo28

@vilakshan.s 3 месяца назад

As per leetcode looks like length of string can go till 5 * 10^4. So containsValue() can potentially end up doing nested looping with O(n) time complexity. Maybe we can improve this by having another reverse HashMap to improve the look up time. SpaceWise it will be 2X but I guess space is much cheaper than time :)

@nikoo28 Месяц назад

Even if the string length is huge, you only have 256 different characters. This is almost constant time.

@adveshdarvekar7733 Месяц назад

If you are coding in c++, you will need 2 hashmaps as you can't make sure the letter is not present in the key as well as the value.

@plutomessi21 11 месяцев назад

bhaiya this code passed 35/44 test cases class Solution { public boolean isIsomorphic(String s, String t) { ArrayList s1 = new ArrayList(); ArrayList s2 = new ArrayList(); int count = 1; for (int i = 1; i < s.length(); i++) { if (s.charAt(i) == s.charAt(i - 1)) { count++; } else { s1.add(count); count = 1; } } // s1.add(count); int count1 = 1; for (int i = 1; i < t.length(); i++) { if (t.charAt(i) == t.charAt(i - 1)) { count1++; } else { s2.add(count1); count1 = 1; } } s2.add(count1); return s1.equals(s2); } }

@nikoo28 10 месяцев назад

have a look at the code in the video description. You will find a github link. That code passes all cases :)

@plutomessi21 10 месяцев назад

@@nikoo28 thank you bhaiya

@dobermanbruce2397 Год назад

😍😍😍😍😍😍😍😍😍😍😍

@filmonghebremariam8981 6 месяцев назад

Are "afa" and "dde" Isomorphic or not?

@nikoo28 5 месяцев назад

they are not

@user-fq5wj3fj6d 9 месяцев назад

Will this code pass the test case s = "12" t = "\u0067\u0068"

@nikoo28 9 месяцев назад

did you try it out?

@mstinku9003 2 месяца назад

easy way to solve this is l=len(set(zip(s,t)) a=len(s) b=len(t) return l==a==b: how easy it is using length

@abhishekj2096 Месяц назад

This solution has runtime of 10ms and beats only 68%. Do you have a faster solution?

@nikoo28 Месяц назад

don't go by these numbers you see on leetcode. If your solution is accepted, it is usually a good enough solution. The runtime usually depends on a lot of things: - the startup time of the VM - the language choice - the processor of the VM - the version of software stack

@ArunKumar-gx8iv 5 месяцев назад

public boolean isIsomorphic(String s, String t) { int n1 = s.length(); int n2 = t.length(); if (n1 != n2) { return false; } HashMap mapST = new HashMap(); HashMap mapTS = new HashMap(); for (int i = 0; i < n1; i++) { char c1 = s.charAt(i); char c2 = t.charAt(i); if (mapTS.containsKey(c1) && mapTS.get(c1) != c2) { return false; } if (mapST.containsKey(c2) && mapST.get(c2) != c1) { return false; } mapTS.put(c1, c2); mapST.put(c2, c1); } return true; }

@delhidhamkhatushyam31 10 месяцев назад

how Paper and Title is isomorphic string you are teching wrong to students

@Coder_421 5 месяцев назад

very bad video

@nikoo28 5 месяцев назад

can you please let me know which part was difficult to understand?

@Coder_421 5 месяцев назад

@@nikoo28 first description part it's self u confused

@nikoo28 5 месяцев назад

which timestamp is confusing you? I added 4 different test cases to clear any confusion.

@Coder_421 5 месяцев назад

@@nikoo28 paper title how e r l e can be mapped e is common 4 case also true

@nikoo28 5 месяцев назад

@@Coder_421 if "paper" is your start string, you are mapping E -> L, and R -> E but if "title" is your start string, then you map L -> E and E -> R You are mapping different characters. But in case 4, when you start from "kikp" you are mapping the same character K once to B and then to D. This is not allowed.

@anveshsrivastava7786 18 дней назад

won't the time complexity be O(N^2) as the the containsValue() method goes through all the key value pairs in a hashmap? can someone please clarify

@sidharthan3349 3 дня назад

yes same doubt

@sidharthan3349 3 дня назад

@nikoo28 can you please reply

@vivekkumaryadav9862 11 месяцев назад

def isIsomorphic(self, s, t): map1 = [] map2 = [] for idx in s: map1.append(s.index(idx)) for idx in t: map2.append(t.index(idx)) if map1 == map2: return True return False

@Krixnbhakt 5 месяцев назад

I'm not able to understand the second else condition - else{ char mappedCharacter = charMappingMap.get(original); if (mappedCharacter != replacement)return false;}