VALID WORD ABBREVIATION | LEETCODE # 408 | PYTHON TWO POINTERS SOLUTION

In this video we are solving a very popular Facebook interview question: Valid Word Abbreviation (Leetcode # 408).
Despite being marked as an Easy level question, this one is definitely more of a medium as there are quite a few edge cases to take care of and it makes this problem quite annoying to deal with. We can solve it using a pretty straightforward two pointer solution though. Stay tuned to find out how!

[@ReleaseTheKraken25]

Starting my meta tagged journey. I'm all in, if I get the job, I'm coming back to thank you.

[@omarllama]

I got this today at Meta interview.

[@gangliums]

@@omarllama was it during tech screen? was it accompanied with a medium?

[@omarllama]

@@gangliums Yes it was screening. I got another easy problem (recursion/stack).

[@diablociscogey]

@@omarllama i'd got the same questions for screening too. are you on discord ?

[@omarllama]

@@diablociscogey I am not on Discord but I can make an account if there are interesting things there :) Since I got ghosted by the recruiter I stopped looking for interviews, going to do a Postdoc.

[@OREdwardsJR]

> IDK who graded this on leetcode but I think they're wrong.. Yes, I agree lol. Conceptually, it's easier but it's still tricky enough to be medium. Thanks for the clear explanation!

[@krishanakhatri4603]

Crystal Clear Explanation!! 🖤

[@akshayakumar9365]

Thanks for the explanation!! Should we not have an extra check "if word_ptr >= len(word) return false" after the words_ptr=steps? because what if abbr had a greater step value than the whole word?

[@AustinAtchley]

It's covered by the while condition

[@ainsdale7752]

Please could you explain the code on line 13 : "steps *10" ....why 10?

[@namratasukanya8424]

we want to get 12 together and not just 1 and 2 separately(abbr='i12iz4n'). Like in ex- word='internationalization', abbr='i12iz4n'

[@izekoreric1310]

I know it's been a year lol! But this is for anybody in the future. Line 13 is used to get a sequence of digits from a string. the steps * 10 creates a space for the next number in the sequence and + int(abbr[abbr_ptr]) adds the next number in the squence. for example: at first steps is 0 and int(abbr[abbr_ptr]) is 1 -> 0 * 10 is 0 then + 1 = 1 (first number in the sequence) next steps is 1 and int(abbr[abbr_ptr]) is 2 -> 1 * 10 is 10 (so the zero at the end creates the space for the next number in the sequence) then + 2 = 12. I hope this helps and I have not over complicate things lol!

[@huachen9747]

@@izekoreric1310thank you! This helped me

[@CompulsiveProgrammerLear-qm6hj]

​@@izekoreric1310 Indeed, it's basically the same than let numStr = ''; while (abbrIndex < abbr.length && !isNaN(abbr[abbrIndex])) { numStr += abbr[abbrIndex]; abbrIndex++; } let num = parseInt(numStr); BUT, that code approach is less memory efficient than the loop and accumulation approach (num = num * 10 + parseInt(abbr[abbrIndex])

[@aribasiebel]

Subscribed after watching this soln. Great job!

[@crackfaang]

Thanks! Welcome to the channel

[@dystopianNinja1289]

Same lol! this guy needs more exposure.

[@sarayarmohammadi3376]

Thank you

[@solar679]

Please explain line 13

[@aribasiebel]

"123" => 123 at each iteration you need to multiply the 'sum' by 10 so you will get 0*10 + int(1) => 1*10 + int(2) => 12*10 + int(3)

[@subee128]

Thanks

[@Aureole62]

I think there is an error on line 9. It should be: if int(abbr[abbr_ptr]) == 0: instead of if abbr[abbr_ptr] == 0:

[@Ankit-hs9nb]

the time complexity would be O(nlogn)? can you please explain how time complexity is O(n)?

[@crackfaang]

It can’t be nlogn, there’s no log n portion here. The o(n) because in the worst case the word and the abbreviation are the same word (ie no abbreviations). Here you need to check every single character one by one to determine they are the same

[@Ankit-hs9nb]

Got it! Thanks! Recently found your channel and it is very helpful!

[@AmolGautam]

The test cases have been changed now , so this solution no longer works. I still like the approach to the solution.

[@3rd_iimpact]

Worked for me.

[@ed2023bc]

Too fast. Not everybody has solved it for 56 times and now is bored with it.