@@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)
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
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)
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
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
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.
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)).
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
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.
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
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.
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)
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.
Wc lc number?
Can you say which one?
which one?
@@stcattc 1768
Great video as always ,
I think One pointer will do the job we don't need two
could you explain ?
@@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)
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
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)
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
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
This was a simple and easy to understand solution. Thanks!
go for the word with shorter length to loop and then concat what is left on the longer word
This is exactly what I did
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
@NeetCodeIO does the interviewer except us to do it in 2 pointer even though we can se 1 pointer?
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.
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)).
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
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
Can anybody explain why converting string to list and then converting list to string is more efficient in python.
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.
@@adama7752 thanks
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
Hey Neetcode, Can you please solve this problem 662. Maximum Width of Binary Tree?
How'd you know that was gonna be todays daily problem 😉
i solved it with a stringbuilder in java idk if that's a correct approach
Leetcode problem number 2096 please!!!
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
Do we need both i and j ?
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.
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)
@@patchouli9 i did the LL way where I used 2 while loops to exhaust the remaining string
Aliens 👽👽 attendance taken by here
Anyone tried this in java with Stringbuilder and substring
I have a question. Do Google know it is you(from your voice and such)
first