Maximum Score Words Formed By Letters - Leetcode 1255

Maximum Score Words Formed By Letters - Leetcode 1255 - Python

Рет қаралды 9,970

NeetCodeIO

Күн бұрын

Пікірлер: 34

@BilalShaikh-tn9wu 6 ай бұрын

this one was 10x easier than yesterdays & its a hard?? crazy

@pastori2672 6 ай бұрын

tf do you mean yesterday was a simple backtracking problem sure the most optimal solution is hard to come up with but a simple backtracking solution passes

@EduarteBDO 6 ай бұрын

@@pastori2672 yesterday was not that simple, if you miss to account duplicate you would end up in a bunch of edge cases without knowing why. that's what happened with me.

@erminiottone 6 ай бұрын

🤯

@hamirmahal 6 ай бұрын

I really liked the rationale for not pre-computing each word's score. Thanks for including it.

@MP-ny3ep 6 ай бұрын

Beautiful explanation. Thank you

@joydeeprony89 6 ай бұрын

this is the first time I did not understand your explanation in the first go.

@sophiophile 5 ай бұрын

I think python lets you just subtract the counters `if can_form_word()`, no need to make the loop explicit.

@tusov8899 6 ай бұрын

Is the space complexity should be O(n +26)? n is for recursive stack and 26 for the letter_cnt. I think we can ignore the space created in the helper function like word_cnt (O(26) if considered) please correct me if I am wrong. Thanks

@gameacc6079 6 ай бұрын

W is from Counter(W), the length of the longest word. It is used in the computation of word_cnt

@chien-yuyeh9386 6 ай бұрын

Thanks!

@corrogist692 6 ай бұрын

I did not add back the letters, but created a copy of the counter (since its of length 26 anyway) before the subtractions, then pass the new counter to the backtracking function as a para. Would this be slightly more efficient?

@DNKF 6 ай бұрын

Could you try the 332 Reconstruct Itinerary using Hierholzer's algorithm please? LC new test case makes the previous solution failed.

@n2ck 6 ай бұрын

his code still works but in the dfs body you just add a failedneighbors set so you can skip neighbors that you know wont work. class Solution: def findItinerary(self, tickets: List[List[str]]) -> List[str]: tickets.sort() # build graph graph = defaultdict(list) # for now Str --> [Listof Str] for src, dst in tickets: graph[src].append(dst) def dfs(currAirport, currAns): if len(currAns) == len(tickets) + 1: return currAns if currAirport not in graph: return None temp = graph[currAirport].copy() failedneighbors = set() for i, nei in enumerate(temp): if nei in failedneighbors: continue graph[currAirport].pop(i) currAns.append(nei) res = dfs(nei, currAns) if res: return res failedneighbors.add(nei) graph[currAirport].insert(i, nei) currAns.pop() return None return dfs('JFK', ['JFK'])

@krateskim4169 6 ай бұрын

Thank you so much

@hithambasheir3283 6 ай бұрын

I tried to be smart by adding a memo for if a word is valid or not, not knowing that this will miss for other cases, took me so long to figure it out 🤦‍♂

@rostislav_engineer 6 ай бұрын

thanks for this video!

@ywsoliman 6 ай бұрын

Can't we use memoization for better time complexity?

@pastori2672 6 ай бұрын

so happy to solve this on my own 🙂

@varunpalsingh3822 6 ай бұрын

I didn't understand the space complexity part, firstly, len(word_cnt) will never exceed the 26, we doesn't include letter_cnt into the space complexity, then we are considering the word_cnt, and secondly, we were given words so why we are considering it to include in space complexity ??

@NeetCodeIO 6 ай бұрын

Length of words determines size of call stack.

@varunpalsingh3822 6 ай бұрын

@@NeetCodeIO ya now got it 👍🏻

@Perry-tf2pr 6 ай бұрын

Can we first include word[w] then add score and cnt last exclude word[x] in backtrack method?

@Munchen888 6 ай бұрын

I think if you want you can initially skip and then include if every single char in hashmap. But I doubt about base case 🧐 If I’m wrong correct me please. If we are at last word thus we should to count total score of word. Count using our score map and return … 🙂‍↔️

@Perry-tf2pr 6 ай бұрын

@@Munchen888 If valid then can be but invalid I initially set 0 . yea passed . If didn’t initiall set,it will raise exception

@albedo9617 6 ай бұрын

Might be a basic question but why are we increasing the letter_cnt on line 28 again. We've already made the recursive calls for both the cases on line 22 and 26 already. So we'll be sending the reduced count to 26 anyway and increasing the count shouldn't matter? I'm coding this in java tho

@AMakYu 6 ай бұрын

As you are moving back up the recursive stack, you must ensure that the letter count is consistent with where you are in the decision tree. If you only decrement, then when you go back up the stack and go down a different branch in the decision tree, the letter count will not be consistent anymore and it may think the following words are invalid because of it. Resetting the state as you go back up the stack is important and is part of the "backtracking".

@albedo9617 6 ай бұрын

@@AMakYu can you check why this one works even though I'm not increasing the count again? class Solution { public int maxScoreWords(String[] words, char[] letters, int[] score) { HashMap charCounter = new HashMap(); for(int i = 0; i < letters.length;i ++){ charCounter.put(letters[i], charCounter.getOrDefault(letters[i],0) + 1); } return solver(words,score, 0, charCounter); } public int solver(String[] words, int[] score, int index, HashMap counter){ if(index == words.length){ return 0; } int s1 = solver(words,score,index+1,new HashMap(counter)); int s2 = 0; int tempScore = 0; if(canWordBeFormed(words[index], counter)){ System.out.println("Word formed"); tempScore = getWordScore(words[index],score); System.out.println(tempScore); s2 = tempScore + solver(words, score, index+1,counter); } return Math.max(s1,s2); } public boolean canWordBeFormed(String word, HashMap counter){ for(int i = 0 ; i < word.length(); i++){ if(counter.get(word.charAt(i)) == null || counter.get(word.charAt(i))