Isomorphic Strings - Leetcode 205 - Python
Vložit
- čas přidán 5. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
⭐ BLIND-75 PLAYLIST: • Two Sum - Leetcode 1 -...
💡 CODING SOLUTIONS: • Coding Interview Solut...
💡 DYNAMIC PROGRAMMING PLAYLIST: • House Robber - Leetco...
🌲 TREE PLAYLIST: • Invert Binary Tree - D...
💡 GRAPH PLAYLIST: • Course Schedule - Grap...
💡 BACKTRACKING PLAYLIST: • Word Search - Backtrac...
💡 LINKED LIST PLAYLIST: • Reverse Linked List - ...
💡 BINARY SEARCH PLAYLIST: • Binary Search
📚 STACK PLAYLIST: • Stack Problems
Problem Link: leetcode.com/problems/isomorp...
0:00 - Read the problem
0:45 - Drawing Explanation
6:32 - Coding Explanation
leetcode 205
This question was identified as a facebook coding interview question from here: github.com/xizhengszhang/Leet...
#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
⭐ BLIND-75 PLAYLIST: czcams.com/video/KLlXCFG5TnA/video.html
such an easy solution, i was reading this problem and just had no idea what isomorhpic was or how to even remotely solve it. thanks bro
Your videos are seriously top notch, there are so many other tutorials out there that essentially read the code line by line. But you provide an intuitive approach to how to solve the problem, in a way that similar approach can also be applied to similar problems.
I'm going to keep watching most likely all of your videos and most likely subscribe on your website as well just to be able to go through the material. The quality really speaks for itself
Thank you
Great Work! I love your videos. I often watch them to practice my English Speaking by repeating your explanations. It really helps. For this question, you can use ONE DICTIONARY and check duplicates in its values.
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
match = dict()
for index in range(len(s)):
if s[index] not in match:
match[s[index]] = t[index] # new map
else:
if t[index] != match[s[index]]: # check existing map
return False
values = match.values()
return len(set(values)) == len(values) # check if any duplicates
O(n) space and O(1) in time complexity ?
In my opinion, your explanation is brilliant, Thank you a lot!
I am addicted to your channel. great work
Amazing question..this is why Facebook is my favorite tool to generate isomorphic strings.
Om pretty sure you can use one map and store em in key val pair and check if the current char in on of string != to the prev value in the other str
Thanks for your intuition, which inspired me to come out with an approach to this problem. I tried Try and Except and it works too.
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
dic = {}
for i in range(len(s)):
if s[i] not in dic and t[i] not in dic.values():
dic[s[i]] = t[i] #create hashtable
else:
try:
if t[i] != dic[s[i]]:
return False
except:
return False
return True
Great solution! I love your videos.
Great explanation, thanks bro!
i couldn't understand the question from leetcode so i had to come here.
Thank you for making me understand
You need only one dict for this task.
just check, that account of unique characters is the smame
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
d = {}
for i, n in enumerate(s):
if n not in d: d[n]=t[i]
else:
if d[n] != t[i]:
return False
return len(d.keys()) == len(set(d.values()))
yeah you can use Counter and make it less lines
I thought the same and checking anyone mentioned the same in the comment section :)
you are a life saver!
Thanks for the sol 🙏
you can do it without reverse map. if you do check both strings: isIsomorphic(s,t) && isIsomorphic(t,s) - makes impl simpler!
جميل جدا. مشكور
Great 👍 Thanks
Suggestion: Reconstruct Itinerary (Graph)
Not Working Your code ....giving error in 3rd example of paper to title
what to do ?
You saved my life!
is it O(1) space as worst case the dictionary will always be of size 128 (ascii)?
Thanks!
Great Explanation. I'm wonder if there is any other Optimal solution.
You can solve it with one hashmap only: look at my solution here:
leetcode.com/problems/isomorphic-strings/discuss/2298081/C-one-Map-solution
if i'm not mistaken, is time complexity O(n) and space complexity O(n) as well?
is it less efficient to do it in just one mapping and check while mapping if key already exits or value already exists then return false ? or big(O)will be bad in my case
I tried this and had a runtime error
Thank you. I finally understand what is isomorphic haha. pretty good job man. thank you so much.
great thank you
thanks
here is my solution
def isomerphic(a,b):
map1=[]
map2=[]
for idx in a:
map1.append(a.index(idx))
for idx in b:
map2.append(b.index(idx))
print(map1)
print(map2)
if map1==map2:
return True
return False
a=("bar")
b=("foo")
print(isomerphic(a,b))
Using this code it seems to return true for "babc"/"baba". If I'm reading this right, it doesn't seem to do a check on the last character.
It does ,
As we maintain 2 diff map one for babc and one for baba
You will have b-->b, a-->a and c--->a in the first Map and in the secondMap you have b-->b,a-->a,(a--->c) this check will fail and returns false.
in 3:29 you could just use this example :
s =
"badc"
t =
"baba"
can anybody help me by explaining whd did we only tranverse string s and not string t
u use both at same time as they are the same size
hmm to me, this questions is tricky and harder than other easy questions
Hi. I am new to Python. Can anyone explain me this line?
if ((c1 in mapST and mapST[c1] != c2) or
(c2 in mapTS and mapTS[c2] != c1)):
This is the most efficent solution i guess:
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
return len(set(zip(s,t))) == len(set(s)) == len(set(t))
NOTE: THIS SOLUTION IS NOT CODED BY ME.
one map and one set is enough
Hey, you missed one Condition i.e. "No two characters may map to the same character" for BAR you mapped (a-> o and r->o).
Will I ever be as clever as you? :(
how bout now bro?
@@HikmalPramudya Haha, since then I've manage to get my first internship as a full stack developer! I guess hardwork pays in the end. Still, not as smart as you tho, but maybe one day :D
@@emanuelvidalrm thank for your answer.. thats build my confidence to be like you. as now i still lack of confidence cuz this leetcode complication hahaha. hopefully i can be like you one year later
class Solution {
public boolean isIsomorphic(String s, String t) {
if(s.length()!=t.length()) return false;
HashMap map=new HashMap();
for(int i=0;i
can we just use 1 map :-?
@Land Keeper - you can do that. In foo and bar example, try to insert f : o#, o# : f, etc. in hashmap.Then, you will see why they are not isomorphic. However, I prefer to solve with 2 hashmap approach which is more cleaner.
A rather sly solution from my side😂. I have managed to use a single map, but I use two traversals. (C++ solution)
class Solution {
public:
bool check(string s, string t)
{
mapmp;
for(int i=0;i
More optimized solution:
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
map = {}
for i in range(len(s)):
if s[i] not in map:
if t[i] not in map.values():
map[s[i]] = t[i]
else:
return False
else:
if t[i] != map[s[i]]:
return False
return True
`if t[i] not in map.values()`
isn't this operation O(n) time complexity?
DOUBTTTT !!!!!!
bruh how can you check the mapping condition ,(i.e. if loop ) because the mapping is not even there, meaning the hashmaps mapST, mapTS were empty right ?? so how can you check the if condition without adding elements in the map itself.
A solution using one HashMap:
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
charMap = {}
if len(s) != len(t):
return False
for i, ch in enumerate(s):
if ch in charMap:
if charMap[ch] != t[i]:
return False
else:
if t[i] in charMap.values():
return False
charMap[ch] = t[i]
return True
This solution has O(n^2) complexity because iterating over values of map is O(n) in the worst case. But the direction is right. I was able to pull this off in O(n) by using a map + hashset to store values mapped in t string
My solution with more explicit tests for possible cases:
def isIsomorphic(self, s: str, t: str) -> bool:
s_instances = {letter: None for letter in set(s)}
for idx, val in enumerate(t):
if not s_instances[s[idx]] and val in s_instances.values():
return False
elif s_instances[s[idx]] and s_instances[s[idx]] != val:
return False
elif not s_instances[s[idx]] and val not in s_instances.values():
s_instances[s[idx]] = val
return True
whot an accent!!!!!!
you live and you learn ... fk me
if Len(set(str1))==Len(set(str2)):
TRUE
else:
FALSE
"bbbaaaba"
"aaabbbba"
this case will fail!!
@@YasirYSR yeah I just checked😬
easy solution
const hash = new Map();
if(new Set(s).size != new Set(t).size) return false;
for(let i = 0; i < s.length; i++){
if(!hash.has(s[i])) {
hash.set(s[i], t[i]);
} else if(hash.get(s[i]) != t[i]) {
return false;
}
}
return true;
// Java Code :
class Solution {
public boolean isIsomorphic(String s, String t) {
// HashMap NC
HashMap mapST = new HashMap();
HashMap mapTS = new HashMap();
int n = s.length(); // t.length() == s.length() !
for(int idx = 0; idx < n; idx++){
char st = s.charAt(idx);
char ts = t.charAt(idx);
if((mapST.containsKey(st) && mapST.get(st) != ts) ||
(mapTS.containsKey(ts) && mapTS.get(ts) != st)){
return false;
}
mapST.put(st, ts);
mapTS.put(ts, st);
}
return true; // TC = SC = O(n) !
}
}