Maximum Score Words Formed By Letters - Leetcode 1255 - Python

[@BilalShaikh-tn9wu]

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

[@pastori2672]

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]

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

🤯

[@csam11100]

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]

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

[@hamirmahal]

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

[@MP-ny3ep]

Beautiful explanation. Thank you

[@sophiophile]

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

[@DNKF]

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

[@n2ck]

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'])

[@ywsoliman]

Can't we use memoization for better time complexity?

[@chien-yuyeh9386]

Thanks!

[@corrogist692]

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?

[@varunpalsingh3822]

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]

Length of words determines size of call stack.

[@varunpalsingh3822]

@@NeetCodeIO ya now got it 👍🏻

[@hithambasheir3283]

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 🤦‍♂

[@toterG0tt]

Thank you!

[@rostislav_engineer]

thanks for this video!

[@joydeeprony89]

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

[@pastori2672]

so happy to solve this on my own 🙂

[@albedo9617]

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]

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]

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

[@Perry-tf2pr]

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

[@Munchen888]

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]

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

[@HolaAmigohehe]

Cant we memoize this?

[@galkk3]

I think I did very similar but my runtime is about 1000 ms, how is it possible?

[@ajinzrathod]

TIP: If you first backtrack the excluded ones and then backtrack the included ones, you won't need to adjust the count again.

[@karlebh]

couple extra dss 😁

[@venky3639]

Damn i couldn't understand that one

[@krateskim4169]

Thank you so much