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
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
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; } }
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())
@@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
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 :)
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
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
Sorry, but you don't need 2 hash tables. Amortized Worst Case dict for "k in d" is O(n). It isn't O(1). Based on this is better to use set()==set(). Will be better based on the Big O notation. So one dict + sets class Solution: def wordPattern(self, pattern: str, s: str) -> bool: A,dct = s.split(" "),{} if len(pattern) != len(A) or len(set(A))!=len(set(pattern)): return False for i,v in enumerate(pattern): if v not in dct: dct[v]=A[i] elif dct[v]!=A[i]: return False return True
Your videos are better than leetcode premium.
leetcoding with a 🤩Google Engineer 🤩 so very kind of you
Hey I know you've gotta fulltime job now so I really appreciate that you're still putting out content
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
I found you today, thank you sooo much.
please do 373.Find K Pairs with Smallest Sums! Love your content!
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
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
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;
}
}
Been addicted to this channel for the past two days
this problem is exactly same as 205. Isomorphic Strings except the words and the small use of split function.
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
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
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 UA-cam 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
Hey, nice video. In what program do you draw?
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.
For the space complexity we should have O(n) only instead of O(n+m) when n = number of words in s
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
}
}
Just following ur content regularly nothing else love u for the amazing work u do
Bravo! this is impressive.
Clean solution! Nice.
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 :)
Amazing Explanation ✌️
yes it does and its pretty efficient!
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
saying that i love this channel is literally saying nothing :')))
Can someone confirm , if the logic is similar to isomorphic strings?
Yes
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;
};
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
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
taking lessons from google employer
Sorry, but you don't need 2 hash tables. Amortized Worst Case dict for "k in d" is O(n). It isn't O(1).
Based on this is better to use set()==set().
Will be better based on the Big O notation.
So one dict + sets
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
A,dct = s.split(" "),{}
if len(pattern) != len(A) or len(set(A))!=len(set(pattern)):
return False
for i,v in enumerate(pattern):
if v not in dct:
dct[v]=A[i]
elif dct[v]!=A[i]:
return False
return True