Merge Strings Alternately - Leetcode 1768 - Python

[@def__init]

Was asked a LC hard in an interview today that you covered. Hoping the rest of the rounds go well, so thankful for the content.

[@stcattc]

Wc lc number?

[@heyyayesh]

Can you say which one?

[@mirkelor]

which one?

[@gabe5225]

@@stcattc 1768

[@jagannthaja7904]

Would love and appreciate a video on all the basics concepts of data structures and algorithms and there uses. Would help lot of non cs students 🙏🙏 Edited: I think u already hav such videos like big O for coding interviews Need that kind of videos for DSA

[@m.kamalali]

Great video as always , I think One pointer will do the job we don't need two

[@dineshsenthil1237]

could you explain ?

[@t.r.r901]

@@dineshsenthil1237 I know I'm a tad late but he means (I think) having one pointer that goes throughs and appends each element to the answer. I did it this way but its complexity isn't great. Here's my code if that helps explaining at all :) def mergeAlternately(self, word1, word2): p=0 ans = [] len1, len2 = len(word1), len(word2) while p < len1 or p < len2: if p < len1: ans.append(word1[p]) if p < len2: ans.append(word2[p]) p += 1 return ''.join(ans)

[@smitpatel7930]

True Buddy Right now I tried and it worked fine class Solution(object): def mergeAlternately(self, word1, word2): """ :type word1: str :type word2: str :rtype: str """ i=0 finalstring=[] while i

[@johnpulawski35]

yah you can do one pointer, add one character from word1 and one character from word2, then just append the remainder of both strings after looping (if no remainder nothing gets added)

[@helloworldcsofficial]

This was a simple and easy to understand solution. Thanks!

[@abdullahqureshi7165]

This was my solution class Solution: def mergeAlternately(self, word1: str, word2: str) -> str: n1 = 0 n2 = 0 res = '' while n1 < len(word1) or n2 < len(word2): if n1 > len(word2) - 1: res += word1[n1] n1 += 1 continue if n2 > len(word1) - 1: res += word2[n2] n2 += 1 continue res += word1[n1] + word2[n2] n1 += 1 n2 += 1 return res

[@NeoGame1000]

Hi NeetCode, could you please explain why did you assess the time complexity as O(n + m), and not as O(Max(n,m). Because basically the algorithm will loop at max Math.Max(n, m) if we are using while with two conditions.

[@S3aw0lf]

In this case we are iterating over both the strings atleast once in our while loop because we need all the characters from both strings combined.If we were asked to append only the alternating characters for eg. a="abcd", b="pqr" and result = "aqcd" then it would have been O(Max(m,n)).

[@shubhambiswas3723]

go for the word with shorter length to loop and then concat what is left on the longer word

[@samuelogunwale2483]

This is exactly what I did

[@ibnjay7]

class Solution: def mergeAlternately(self, word1: str, word2: str) -> str: output = "" len1 = len(word1) len2 = len(word2) pointer1 = 0 pointer2 = 0 for i in range(len1+len2): if pointer1 < len1: output = output + word1[pointer1] pointer1 = pointer1+1 if pointer2 < len2: output = output + word2[pointer2] pointer2 = pointer2 +1 return output I did it such an unpythonic way

[@hawksawed]

Same. But I think this may be a slightly more efficient version of yours: onesize = len(word1) twosize = len(word2) maxsize = max(onesize, twosize) x = "" for i in range(maxsize): if i < onesize: x += word1[i] if i < twosize: x += word2[i] return x

[@phongtranquoc7557]

another approach with time complexity O(m+n): "class Solution { public String mergeAlternately(String word1, String word2) { String ans = ""; int length1 = word1.length(); int length2 = word2.length(); int index = 0; for(int i = 0; i < length1; i++) { ans += word1.charAt(i); if(i == index && i

[@redone729]

Why are you using two i and j counters when they are exactly the same? j can be removed completely and be replaced by i

[@adhivp5594]

Can anybody explain why converting string to list and then converting list to string is more efficient in python.

[@adama7752]

In python strings are immutable (cannot be changed), instead a new string is created. So as you append a char, python copied your old string into a new string with 1 extra space where your char is appended. When you join a list I'm assuming it's a built-in function that will allocate memory required for the whole list.

[@adhivp5594]

@@adama7752 thanks

[@bort-oy6ux]

i solved it with a stringbuilder in java idk if that's a correct approach

[@marwanahmed2657]

Hey Neetcode, Can you please solve this problem 662. Maximum Width of Binary Tree?

[@NeetCodeIO]

How'd you know that was gonna be todays daily problem 😉

[@RockuHD]

Try pre sizing the list. Bet that speeds it up a fair bit. Also one index. Better yet use c++, malloc the size of memory you need(+1 for the null terminator), the set the char at each memory address and return a const char* that points to the start of the string

[@Nisha.......]

Leetcode problem number 2096 please!!!

[@aribasiebel]

Do we need both i and j ?

[@patchouli9]

You can use a single i and take from both strings at the same index, starting with word1, then at the end compare the lengths of the strings and take the rest of the longer one. The i,j way is done is similar to a Linked List problem where you would pick from two LL into a single LL and just concat at the end. I think the i,j way is less error prone and is the way I prefer doing it, also easily applicable to various LL problems.

[@nikhil_a01]

You can do it with a single pointer as @patchouli said. I also prefer to use i and j though. I think it's clearer and it's a more general pattern. But if you do use a single pointer, you don't need to compare the lengths of the strings at the end. You can still use the slicing. The code is below. (And before anyone guesses that this won't work, yes I did submit this). class Solution: def mergeAlternately(self, word1: str, word2: str) -> str: i = 0 res = [] while i < len(word1) and i < len(word2): res.append(word1[i]) res.append(word2[i]) i += 1 res.append(word1[i:]) res.append(word2[i:]) return "".join(res)

[@utkarshdewan8736]

@@patchouli9 i did the LL way where I used 2 while loops to exhaust the remaining string

[@808brotherstv4]

Anyone tried this in java with Stringbuilder and substring

[@infinitygod5379]

I have a question. Do Google know it is you(from your voice and such)

[@vishnuvardhan2687]

Aliens 👽👽 attendance taken by here

[@hypermeero4782]

first