Word Pattern - Leetcode 290 - Python

Поделиться
HTML-код
  • Опубликовано: 13 дек 2024

Комментарии • 44

  • @henryrussell7392
    @henryrussell7392 2 года назад +41

    Your videos are better than leetcode premium.

  • @ashwinsingh1325
    @ashwinsingh1325 2 года назад +21

    Hey I know you've gotta fulltime job now so I really appreciate that you're still putting out content

  • @awarepenguin3376
    @awarepenguin3376 2 года назад +41

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

  • @EricCycles
    @EricCycles 2 года назад +8

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

    • @Millicx
      @Millicx 2 года назад +2

      I was thinking the same, why do we need another hashmap for the same thing

    • @phuongla4512
      @phuongla4512 2 года назад

      why do you have to put words.length != pattern.length() in the loop instead of just checking for it outside before the loop?

    • @aboutvic.
      @aboutvic. 9 месяцев назад

      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.

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

      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

    • @alonerpro
      @alonerpro 2 месяца назад

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

  • @shakhzod_shermatov
    @shakhzod_shermatov 2 месяца назад +1

    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

  • @andreyvalverde4780
    @andreyvalverde4780 2 года назад +4

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

  • @VinayakH
    @VinayakH 2 года назад +3

    I found you today, thank you sooo much.

  • @thaqibm4284
    @thaqibm4284 2 года назад

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

  • @prensapjaimo
    @prensapjaimo 2 года назад

    Been addicted to this channel for the past two days

  • @eraytasay
    @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();
    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;
    }
    }

  • @alonerpro
    @alonerpro 2 месяца назад

    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)

  • @vgsuresh
    @vgsuresh Год назад +2

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

  • @priyankasetiya1358
    @priyankasetiya1358 3 месяца назад

    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

  • @suriyaprakashgopi
    @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

  • @Yashas-z9s
    @Yashas-z9s 2 года назад

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

  • @dbm103
    @dbm103 3 месяца назад

    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

  • @RojinSharma-c8l
    @RojinSharma-c8l 6 месяцев назад

    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

  • @mohithadiyal6083
    @mohithadiyal6083 2 года назад

    Amazing Explanation ✌️

  • @Nick-uo2bi
    @Nick-uo2bi 2 года назад +1

    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.

    • @xiaoruixue3494
      @xiaoruixue3494 2 года назад

      He already had one.

    • @lordsixth5944
      @lordsixth5944 2 года назад

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

  • @kiki-yq1fk
    @kiki-yq1fk 2 года назад

    Clean solution! Nice.

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

    Bravo! this is impressive.

  • @krishnamohantiwari1140
    @krishnamohantiwari1140 2 года назад

    yes it does and its pretty efficient!

  • @Kokurorokuko
    @Kokurorokuko 2 года назад

    Hey, nice video. In what program do you draw?

  • @pa0414
    @pa0414 Год назад

    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

  • @MrVintarb
    @MrVintarb 2 года назад

    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.

  • @jey_n_code
    @jey_n_code Год назад

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

  • @sabu4539
    @sabu4539 Год назад +1

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

  • @RezaE
    @RezaE 2 года назад +3

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

  • @deliarasui1082
    @deliarasui1082 2 года назад

    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!

    • @NeetCode
      @NeetCode  2 года назад +4

      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 :)

  • @priyankasetiya1358
    @priyankasetiya1358 3 месяца назад

    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

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

    Can someone confirm , if the logic is similar to isomorphic strings?

  • @yaswanthkosuru
    @yaswanthkosuru 2 года назад +1

    taking lessons from google employer

  • @vinuset596
    @vinuset596 2 года назад

    Please, write a code that shows how you paid rent when you were unemployed. I want to see something 😪

  • @vshettyvs
    @vshettyvs 2 года назад

    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