we only need 1 hash map for this. Java code: Runs faster than 100% of java solutions public boolean wordPattern(String pattern, String s) { HashMap patternMap = new HashMap(); String[] words = s.split(" "); //if we only have one char and one word if(pattern.length() == 1 && words.length == 1){ return true; } //pattern letter to word matching for(int i = 0; i < pattern.length(); i++){ if(patternMap.containsKey(pattern.charAt(i))){ String theWord = (String)patternMap.get(pattern.charAt(i)); if(!theWord.equals(words[i])){ return false; } }else{ if(patternMap.containsValue(words[i]) || words.length != pattern.length()){ return false; }else{ patternMap.put(pattern.charAt(i), words[i]); } } } return true; }
containsKey() is O(1) but containsValue is an O(n) computation. Every time you attempt to insert a new (key, value) pair, you run this. It's not the best for your runtime.
class Solution: def wordPattern(self, pattern: str, s: str) -> bool: dictionary = {} values = s.split(" ") if len(values)!=len(pattern): return False for i in range(len(pattern)): if pattern[i] in dictionary: if not dictionary[pattern[i]]==values[i]: return False elif values[i] in dictionary.values(): return False else: dictionary[pattern[i]]=values[i] return True
@@amankassahunwassie587 class Solution: def wordPattern(self, pattern: str, s: str) -> bool: d = {} l = 0 ls = s.split() if len(ls) != len(pattern): return False
for i in range(len(pattern)): if pattern[i] not in d.values(): d[ls[i]] = pattern[i] for i in range(len(pattern)): if ls[i] in d.keys(): if pattern[i] == d[ls[i]]: l += 1
return l == len(ls) mine uses 2 for loops still tc = O(n) right? your's seems better
I am not being a nitpicker, but I expected also the solution without using split function, because I solved without using split function, but my solution looks very ugly. Thank you anyways for great explanations! I know you invested a lot of time and effort. My solution without using split in Python: def wordPattern(self, pattern: str, s: str) -> bool: mapP, mapS = {}, {} c, j = 0, 0 n = len(pattern) if ' ' not in s and n > 1: return False if ' ' in s: s += ' ' for i in range(len(s)): if j == n: return False if s[i] == ' ': if ((s[c:i] in mapS and mapS[s[c:i]] != pattern[j]) or (pattern[j] in mapP and mapP[pattern[j]] != s[c:i])): return False mapP[pattern[j]] = s[c:i] mapS[s[c:i]] = pattern[j] c = i + 1 j += 1 return True
It is very good solution thank you for all of your efforts. Your videos help me a lot. I did it very similarly with minor difference. I kept track of mapped letters of pattern using HashSet instead of HasMap but I still used HasMap to map the words with letters. Contains method of set is also O(1) and I think it better not to store the words again. Basicly I think in this way time complexity is the same but it is more efficient in terms of memory. If I think wrong inform me please. class Solution { public boolean wordPattern(String pattern, String s) { var words = s.split("[ ]"); var wordMap = new HashMap(); var mappedChrs = new HashSet(); if (pattern.length() != words.length) return false; for (var i = 0; i < words.length; i++) { var word = words[i]; var patternChr = pattern.charAt(i); if (!wordMap.containsKey(word)) { if (mappedChrs.contains(patternChr)) return false; wordMap.put(word, patternChr); mappedChrs.add(patternChr); } else if (wordMap.get(word) != patternChr) return false; } return true; } }
My solution uses 1 hashmap class Solution: def wordPattern(self, pattern: str, s: str) -> bool: d = {} l = 0 ls = s.split() if len(ls) != len(pattern): return False
for i in range(len(pattern)): if pattern[i] not in d.values(): d[ls[i]] = pattern[i] for i in range(len(pattern)): if ls[i] in d.keys(): if pattern[i] == d[ls[i]]: l += 1
I think timecomplexity will be O(n) instead of O(n+m) because if n and m are not equal then we will return false immediately otherwise we will just iterate once
class Solution: def wordPattern(self, pattern: str, s: str) -> bool: words = s.split(" ") patt = [i for i in pattern] a=[] b=[] for i in patt: a.append(patt.index(i)) for i in words: b.append(words.index(i)) if a==b: return True else: return False
@@xiaoruixue3494 python soln for problem with single hashmap class Solution: def wordPattern(self, pattern: str, s: str) -> bool: if set(list(pattern)).__len__()!=set(s.split(" ")).__len__(): return False dict1 = {} for i,j in zip(pattern,s.split(" ")): dict1[i]=j if " ".join([dict1[i] for i in pattern])==s: return True return False
Wouldn't below work as well, not sure of TC and SC strings = ["cat", "dog", "dog"] patterns = ["a", "b", "b"] def solution(strings, patterns): result = True string_to_pattern = {} pattern_to_string = {}
for i,j in enumerate(strings): if j not in string_to_pattern.keys(): string_to_pattern[j]=[] string_to_pattern[j].append(i) for i,j in enumerate(patterns): if j not in pattern_to_string.keys(): pattern_to_string[j]=[] pattern_to_string[j].append(i) x=str(string_to_pattern.values()) y=str(pattern_to_string.values())
There is a mistake in time complexity analysis. The actual complexity is O(n * m), where n is number of words, and m is width of the longest word. Why? First, on the 11-th line each time we compare word from hash map with word from zip. Second, on the 13-th line because each time when we check w in wordToChar, hash-map doing 2 things: 1) The hash comparison. 2) After checking hash, the words comparison. The comparison is loop with m iterations, and it's nested into zip loop with n iterations.
Hey NeetCode. I had a question not exactly algo related. I took a year off(15 months!) from work due to personal issues and now trying to get back. Would you happen to have any idea if an employment gap is a huge turn off? any response is appreciated. Thanks!
Employment gaps are sometimes a turnoff, but not a huge deal. Especially if you had a good amount of experience before the gap. For my situation, having a gap made things harder, but things still worked out for me. Best of luck, I'm sure it will work out :)
Using a single map class Solution { public boolean wordPattern(String pattern, String s) { String[] splitted = s.split(" "); if(pattern.length()!=splitted.length){ return false; } Map map = new HashMap(); for(int i=0;i
The time complexity should be O(N) not O(N+ M) since if the 2 arrays are unequal we exit anyways. If they are equal we are only going through the string once
Your videos are better than leetcode premium.
Hey I know you've gotta fulltime job now so I really appreciate that you're still putting out content
leetcoding with a 🤩Google Engineer 🤩 so very kind of you
we only need 1 hash map for this. Java code: Runs faster than 100% of java solutions
public boolean wordPattern(String pattern, String s) {
HashMap patternMap = new HashMap();
String[] words = s.split(" ");
//if we only have one char and one word
if(pattern.length() == 1 && words.length == 1){
return true;
}
//pattern letter to word matching
for(int i = 0; i < pattern.length(); i++){
if(patternMap.containsKey(pattern.charAt(i))){
String theWord = (String)patternMap.get(pattern.charAt(i));
if(!theWord.equals(words[i])){
return false;
}
}else{
if(patternMap.containsValue(words[i]) || words.length != pattern.length()){
return false;
}else{
patternMap.put(pattern.charAt(i), words[i]);
}
}
}
return true;
}
I was thinking the same, why do we need another hashmap for the same thing
why do you have to put words.length != pattern.length() in the loop instead of just checking for it outside before the loop?
containsKey() is O(1) but containsValue is an O(n) computation. Every time you attempt to insert a new (key, value) pair, you run this. It's not the best for your runtime.
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
dictionary = {}
values = s.split(" ")
if len(values)!=len(pattern):
return False
for i in range(len(pattern)):
if pattern[i] in dictionary:
if not dictionary[pattern[i]]==values[i]:
return False
elif values[i] in dictionary.values():
return False
else:
dictionary[pattern[i]]=values[i]
return True
@@amankassahunwassie587
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
d = {}
l = 0
ls = s.split()
if len(ls) != len(pattern):
return False
for i in range(len(pattern)):
if pattern[i] not in d.values():
d[ls[i]] = pattern[i]
for i in range(len(pattern)):
if ls[i] in d.keys():
if pattern[i] == d[ls[i]]:
l += 1
return l == len(ls)
mine uses 2 for loops still tc = O(n) right? your's seems better
I am not being a nitpicker, but I expected also the solution without using split function, because I solved without using split function, but my solution looks very ugly.
Thank you anyways for great explanations! I know you invested a lot of time and effort.
My solution without using split in Python:
def wordPattern(self, pattern: str, s: str) -> bool:
mapP, mapS = {}, {}
c, j = 0, 0
n = len(pattern)
if ' ' not in s and n > 1: return False
if ' ' in s: s += ' '
for i in range(len(s)):
if j == n: return False
if s[i] == ' ':
if ((s[c:i] in mapS and mapS[s[c:i]] != pattern[j]) or
(pattern[j] in mapP and mapP[pattern[j]] != s[c:i])):
return False
mapP[pattern[j]] = s[c:i]
mapS[s[c:i]] = pattern[j]
c = i + 1
j += 1
return True
please do 373.Find K Pairs with Smallest Sums! Love your content!
I found you today, thank you sooo much.
Scala Solution:
def wordPattern(pattern: String, s: String): Boolean = {
val S = s.split(" ")
if(pattern.distinct.size != S.distinct.size || pattern.size != S.size){
false
}
else{
pattern.zip(S).distinct.size == S.distinct.size
}
}
Been addicted to this channel for the past two days
It is very good solution thank you for all of your efforts. Your videos help me a lot. I did it very similarly with minor difference. I kept track of mapped letters of pattern using HashSet instead of HasMap but I still used HasMap to map the words with letters. Contains method of set is also O(1) and I think it better not to store the words again. Basicly I think in this way time complexity is the same but it is more efficient in terms of memory. If I think wrong inform me please.
class Solution {
public boolean wordPattern(String pattern, String s)
{
var words = s.split("[ ]");
var wordMap = new HashMap();
var mappedChrs = new HashSet();
if (pattern.length() != words.length)
return false;
for (var i = 0; i < words.length; i++) {
var word = words[i];
var patternChr = pattern.charAt(i);
if (!wordMap.containsKey(word)) {
if (mappedChrs.contains(patternChr))
return false;
wordMap.put(word, patternChr);
mappedChrs.add(patternChr);
}
else if (wordMap.get(word) != patternChr)
return false;
}
return true;
}
}
My solution uses 1 hashmap
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
d = {}
l = 0
ls = s.split()
if len(ls) != len(pattern):
return False
for i in range(len(pattern)):
if pattern[i] not in d.values():
d[ls[i]] = pattern[i]
for i in range(len(pattern)):
if ls[i] in d.keys():
if pattern[i] == d[ls[i]]:
l += 1
return l == len(ls)
tc = sc = O(n)
this problem is exactly same as 205. Isomorphic Strings except the words and the small use of split function.
I think timecomplexity will be O(n) instead of O(n+m) because if n and m are not equal then we will return false immediately otherwise we will just iterate once
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
words = s.split(" ")
patt = [i for i in pattern]
a=[]
b=[]
for i in patt:
a.append(patt.index(i))
for i in words:
b.append(words.index(i))
if a==b:
return True
else:
return False
Just following ur content regularly nothing else love u for the amazing work u do
One Doubt here:
Isn't time complexity and space complexity be O(n) as if we are only processing further if length of both are same
Hey man, I love the theme that you have on your leetcode, code editor. Can you please share the extension or let us know how to put it on
Amazing Explanation ✌️
Please make a complete playlist on DSA and DP in python it will help alot for beginners and there isn't any right now on RUclips in python.
He already had one.
@@xiaoruixue3494
python soln for problem with single hashmap
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
if set(list(pattern)).__len__()!=set(s.split(" ")).__len__():
return False
dict1 = {}
for i,j in zip(pattern,s.split(" ")):
dict1[i]=j
if " ".join([dict1[i] for i in pattern])==s:
return True
return False
Clean solution! Nice.
Bravo! this is impressive.
yes it does and its pretty efficient!
Hey, nice video. In what program do you draw?
Wouldn't below work as well, not sure of TC and SC
strings = ["cat",
"dog",
"dog"]
patterns = ["a",
"b",
"b"]
def solution(strings, patterns):
result = True
string_to_pattern = {}
pattern_to_string = {}
for i,j in enumerate(strings):
if j not in string_to_pattern.keys():
string_to_pattern[j]=[]
string_to_pattern[j].append(i)
for i,j in enumerate(patterns):
if j not in pattern_to_string.keys():
pattern_to_string[j]=[]
pattern_to_string[j].append(i)
x=str(string_to_pattern.values())
y=str(pattern_to_string.values())
return x==y
There is a mistake in time complexity analysis.
The actual complexity is O(n * m), where n is number of words, and m is width of the longest word.
Why?
First, on the 11-th line each time we compare word from hash map with word from zip.
Second, on the 13-th line because each time when we check w in wordToChar, hash-map doing 2 things:
1) The hash comparison.
2) After checking hash, the words comparison.
The comparison is loop with m iterations, and it's nested into zip loop with n iterations.
saying that i love this channel is literally saying nothing :')))
var wordPattern = function(pattern, s) {
const hashmap = new Map();
const splitted = s.split(" ");
if(splitted.length !== pattern.length) return false;
if (new Set(pattern).size !== new Set(splitted).size) return false;
for(let i = 0; i < pattern.length; i++){
if(!hashmap.has(splitted[i])){
hashmap.set(splitted[i], pattern[i])
continue;
}
if((hashmap.get(splitted[i]) !== pattern[i])){
return false;
}
}
return true;
};
For the space complexity we should have O(n) only instead of O(n+m) when n = number of words in s
Hey NeetCode. I had a question not exactly algo related.
I took a year off(15 months!) from work due to personal issues and now trying to get back. Would you
happen to have any idea if an employment gap is a huge turn off? any response is appreciated.
Thanks!
Employment gaps are sometimes a turnoff, but not a huge deal. Especially if you had a good amount of experience before the gap. For my situation, having a gap made things harder, but things still worked out for me.
Best of luck, I'm sure it will work out :)
Using a single map
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] splitted = s.split(" ");
if(pattern.length()!=splitted.length){
return false;
}
Map map = new HashMap();
for(int i=0;i
Can someone confirm , if the logic is similar to isomorphic strings?
Yes
taking lessons from google employer
Please, write a code that shows how you paid rent when you were unemployed. I want to see something 😪
The time complexity should be O(N) not O(N+ M) since if the 2 arrays are unequal we exit anyways. If they are equal we are only going through the string once