Word Pattern - Leetcode 290 - Python

0:00 - Read the problem
2:10 - Drawing Explanation
5:47 - Coding Explanation

leetcode 290

#coding #interview #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[henryrussell]

Your videos are better than leetcode premium.

[ashwinsingh]

Hey I know you've gotta fulltime job now so I really appreciate that you're still putting out content <3 been helping tons with interview prep!

[awarepenguin]

leetcoding with a 🤩Google Engineer 🤩 so very kind of you

[EricCycles]

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<Character, String>();
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++){

String theWord =

return false;
}
}else{
|| words.length != pattern.length()){
return false;
}else{
patternMap.put(pattern.charAt(i), words[i]);
}
}
}
return true;
}

[andreyvalverde]

please do 373.Find K Pairs with Smallest Sums! Love your content!

[VinayakH]

I found you today, thank you sooo much.

[prensapjaimo]

Been addicted to this channel for the past two days

[eraytasay]

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<String, Character>();
var mappedChrs = new HashSet<Character>();

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
return false;

wordMap.put(word, patternChr);
mappedChrs.add(patternChr);
}
else if (wordMap.get(word) != patternChr)
return false;
}

return true;
}
}

[priyankasetiya]

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

[Yashas-zs]

Just following ur content regularly nothing else love u for the amazing work u do

[dbm]

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

[RezaE]

For the space complexity we should have O(n) only instead of O(n+m) when n = number of words in s

[vgsuresh]

this problem is exactly same as 205. Isomorphic Strings except the words and the small use of split function.

[Nick-uobi]

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 YouTube in python.

[thaqibm]

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
}
}

[zvmrbod]

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

[suriyaprakashgopi]

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

[MrVintarb]

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.

[pa]

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]=[]


for i, j in enumerate(patterns):
if j not in pattern_to_string.keys():
pattern_to_string[j]=[]




return x==y

[jey_n_code]

saying that i love this channel is literally saying nothing :')))