Your vedios are really great. In this solution, we append and then copy result string in every iteration which is not optimal, TC will become O(n^2). It is better to start from end of input string, reverse each sub-string and then append it to result string, this will give us TC as O(n)
string reverseWords(std::string s) { int i = 0; int n = s.length(); string ans; while (i < n) { while (i < n && s[i] == ' ') { i++; // skip spaces } if (i >= n) break; int j = i; while (j < n && s[j] != ' ') { j++; // find the end of the word } string word = s.substr(i, j - i); // extract the word if (ans.empty()) { ans = word; // if it's the first word, no need to add space } else { ans = word + " " + ans; // prepend the word } i = j; // move to the next word } return ans; }
For java users here is the code class Solution { public String reverseWords(String s) { char []str=s.toCharArray(); String result="",w=""; int n=s.length(); int i=0,j=0; while(i
Time complexity should be O(n) We are still iterating through the array linearly, and when the j loop is activated, it still linearly searches in the same array but when it reaches a letter/nospace until it reaches '_' (_ is 1 space). , then continues from outer main loop again, the inner loop if it satisfies the condition all the way to the end of len(array). Space should be O(n) since we create a result array, it cannot be O(1) because we are not manipulating the input array in place. Please feel free to correct me if I'm wrong but I am thinking this is correct.
@@manasakaleyanda3963 Nope, it's O(n). Result is basically storing the original string in reverse so it's copying. it will be as long as the original words minus whitespaces.
This isn't working for me. The output is: "blue is sky the the" "world hello hello" "example good a a". The output always duplicate the last word. Edit* Never mind, I miss-placed the i = j + 1 into the final else statement
@@KnowledgeCenter Sir can you please explain what we are doing in s.substr(i,j-1) and result = w + " "+ result , IT should be result + " " + w -- right ?
Hi @Abhishek the video is very good, but I am thinking can we split the string using spaces and rearranging in the reverse order it will do our requirement right.
Yes. That should work. May be a little more space will be required to store all the words after splitting, and then creating the result string from that.
even if I am able to solve the question by myself , I watch your videos because your solution is always better than mine :-)..... I didnt see the O(1) space code.....can you comment it
O(1) or reverse in place is quite easy. you will need to reverse entire string first and then reverse every word in reversed string. def reverse_characters(m, i, j): while i < j: m[i], m[j] = m[j], m[i] i += 1 j -= 1 def reverse_words(message): l = len(message) i = 0 reverse_characters(message, 0, len(message) - 1) for j in range(l+1): if j == l or message[j] == " ": reverse_characters(message, i, j - 1) i = j + 1 return message
How to skip last two words in sentence? My input string is: Hi there. My name is Kalp. This is my lucky day. I like coding so much. This is it. Expected output is: Hi there. name My is Kalp. my is This lucky day. coding like I so much. This is it.
I write a main method after your code. and it doesn't work. It only returns one word of my sentence. public static void main(String[] args) { Scanner keyboard = new Scanner(System.in);
System.out.println("Enter the sentence:"); String sentence = keyboard.next(); String result = reverseWords(sentence); System.out.println(result); } Did I do anything wrong with my main method?
string reverseWords(std::string s) { int i = 0; int n = s.length(); string ans; while (i < n) { while (i < n && s[i] == ' ') { i++; // skip spaces } if (i >= n) break; int j = i; while (j < n && s[j] != ' ') { j++; // find the end of the word } string word = s.substr(i, j - i); // extract the word if (ans.empty()) { ans = word; // if it's the first word, no need to add space } else { ans = word + " " + ans; // prepend the word } i = j; // move to the next word } return ans; }
If you need O(1) space sol:
class Solution {
public:
void reverseword(string &s, int i, int j){ //reverse string from i to j
while(i
isnt the time complexity here O(n^2)?
Your vedios are really great. In this solution, we append and then copy result string in every iteration which is not optimal, TC will become O(n^2). It is better to start from end of input string, reverse each sub-string and then append it to result string, this will give us TC as O(n)
Great Idea!
Reverse itself takes O(N) so if the avg length of a substring is m the total TC will be O(n*m)
The best video explanations I have seen so far.
Glad it was helpful!
I CANT'T THANK YOU ENOUGH I WAS FRUSTRATED FROM AN HOUR OR SO, THANKYOU SO MUCH FOR IMPLEMENTING IT IN JAVA ASWELL😭😭😭😭😭😭
Thanks
class Solution(object):
def reverseWords(self, s):
sp = s.strip().split()
res = ""
i,j=0,len(sp)-1
while i
best video i have found on how to reverse an word
thank u sir...
Thanks.
what is the point of writing 7th line python . when we placed a condition i
string reverseWords(std::string s) {
int i = 0;
int n = s.length();
string ans;
while (i < n) {
while (i < n && s[i] == ' ') {
i++; // skip spaces
}
if (i >= n) break;
int j = i;
while (j < n && s[j] != ' ') {
j++; // find the end of the word
}
string word = s.substr(i, j - i); // extract the word
if (ans.empty()) {
ans = word; // if it's the first word, no need to add space
} else {
ans = word + " " + ans; // prepend the word
}
i = j; // move to the next word
}
return ans;
}
Wow man... Quality content every time
Thanks.
sir, can u add time complexity of every problem in your video that's really help!!
this is the only solution I found where internal methods are not used
What a nice and a easy explanation .
Thank you Sir.
I am wondering can we use stringtok in this question? Yes, it will be space O(n) but can be solved quicker I guess!
bhaiya aap yaha ?
python
class Solution:
def reverseWords(self, s: str) -> str:
return " ".join(list(filter(lambda x: len(x)>0,s.split(" ")))[::-1])
Excellent
Thank you very much
Changing the index value after spaces is like magic
Really awesome 😎
in the solution, line #10 should be int j=i for a single character string.
Also line #15 should be i=j if that falls true.
Ultimate i would say hats off sir👌👌👏👏
Thanks a lot.
For java users here is the code
class Solution {
public String reverseWords(String s) {
char []str=s.toCharArray();
String result="",w="";
int n=s.length();
int i=0,j=0;
while(i
While(i
give a space between the null character initialization.
Good video sir,
Can you write this Java program too:
Input: "This is, the most; particular example!"
Output: "example particular, most the; is This!"
Sir it is difficult for Me to understand the concept why we take subs from (i, j-i) why not from (i,j) in c++
same
because in c++, the second parameter takes the length of the substring and the length of word here is (j-i).
commented using API.
Which api
Time complexity should be
O(n) We are still iterating through the array linearly, and when the j loop is activated,
it still linearly searches in the same array but when it reaches a letter/nospace until it reaches '_' (_ is 1 space). , then continues from outer main loop again, the inner loop if it satisfies the condition all the way to the end of len(array).
Space should be
O(n) since we create a result array, it cannot be O(1) because we are not manipulating the input array in place.
Please feel free to correct me if I'm wrong but I am thinking this is correct.
Space complexity will be O(1) as result is being stored to a constant and same constant gets updated on every iteration.
@@manasakaleyanda3963 Nope, it's O(n). Result is basically storing the original string in reverse so it's copying. it will be as long as the original words minus whitespaces.
thanks for the explanation!!
Welcome.
I REALLY LIKED THE PART WHERE HE EXPLAINED THE CODE IN C++ AND PYTHON
Thanks.
This isn't working for me.
The output is:
"blue is sky the the"
"world hello hello"
"example good a a".
The output always duplicate the last word.
Edit*
Never mind, I miss-placed the i = j + 1 into the final else statement
Really you are the best!. Especially those python solutions
Thanks.
@@KnowledgeCenter Sir can you please explain what we are doing in s.substr(i,j-1) and result = w + " "+ result , IT should be result + " " + w -- right ?
Thank you, was very helpful
Glad to hear!
Thank you. You did in a very clear way.
Glad it was helpful!
video are very helpful.
Glad to hear that
Hi @Abhishek the video is very good, but I am thinking can we split the string using spaces and rearranging in the reverse order it will do our requirement right.
Yes. That should work. May be a little more space will be required to store all the words after splitting, and then creating the result string from that.
even if I am able to solve the question by myself , I watch your videos because your solution is always better than mine :-)..... I didnt see the O(1) space code.....can you comment it
O(1) or reverse in place is quite easy. you will need to reverse entire string first and then reverse every word in reversed string.
def reverse_characters(m, i, j):
while i < j:
m[i], m[j] = m[j], m[i]
i += 1
j -= 1
def reverse_words(message):
l = len(message)
i = 0
reverse_characters(message, 0, len(message) - 1)
for j in range(l+1):
if j == l or message[j] == " ":
reverse_characters(message, i, j - 1)
i = j + 1
return message
@Dmitry That's an excellent idea. Thanks for sharing.
Nice approach. But strings are immutable in python. Solution works if you have list of char
wil your code work if there are spaces in the start ,end and extra spaces un the middle??
@@abhishek_vancedyoutube5935 So, is there any solutions for python with space O(1)? I cannot find one😭
I don't understand why we can't just use trim in java and strip in python to get rid of the leading and trailing spaces.
Awesome explaination !!
Thank You Sir.
Welcome!
sir you r the best sir!
Thanks a lot Sir..
Learn by Doing
At 3:12 'i' variable is looking for space and 'j' variable is looking for non space. Anybody Correct me if i am wrong?
can anyone tell what is the significance of writing if(i>=n)break; here?
it will be really helpful
if you notice the next line is int j = i + 1; so if we dont catch i>= n, j will be out of range of the string by this line charAt(j).
Excellent explanation
Thanks.
Sir so far shortest video from you 😛😛
Trying to decrease video lengths.
@@KnowledgeCenter But please don't compromise on quality sir
Our humble request
Sure.
Nice Video!
C++ Code is not working
s = sentence.split()[::-1]
l = []
for i in s:
l.append(i[::-1])
print('-'.join(l))
please provide the desired code in description box
Code for no extra space
class Solution {
public:
string reverseWords(string s) {
int k=s.size();
int n=k;
s+=" ";
while(n>=0)
{
while(n>=0 && s[n]==' ')
{
n--;
}
if(n=0 && s[j]!=' ')
{
j--;
}
s+=s.substr(j+1,n-j)+" ";
n=j-1;
}
s=s.substr(k+1,s.size()-(k+2));
return s;
}
};
How to skip last two words in sentence?
My input string is: Hi there. My name is Kalp. This is my lucky day. I like coding so much. This is it.
Expected output is: Hi there. name My is Kalp. my is This lucky day. coding like I so much. This is it.
thanks.........
Welcome!!
Thanks
Welcome. Thanks for supporting the channel.
always try to show runtime speed and space after code is submitted
thank you bro, your explanations are so clear
Glad to hear that!
Nice explanation
Thanks for liking
Code is not reversing , please help
this code is not working in leetcode
Just now checked. It works. In C++, Java, Python3. All the three languages. Can you retry.
Sir, there's no doubt that you make a problem look very easy but it will be great if you write code in C language also...plzzzzz
Without STLs, life would become tough. Need to implement whichever container we want to use.
Thanku sir
Welcome.
Perfect
In Leetcode, it gives error for Python3
Time Limit Exceeded
Use strip to get rid of leading and trailing spaces.
This code is useful for Umar the Akmal🤣
Jaduu!
How to write complext code 101
I write a main method after your code. and it doesn't work. It only returns one word of my sentence.
public static void main(String[] args) {
Scanner keyboard = new Scanner(System.in);
System.out.println("Enter the sentence:");
String sentence = keyboard.next();
String result = reverseWords(sentence);
System.out.println(result);
}
Did I do anything wrong with my main method?
Nice explanation. Although I was expecting in-place solution.
string reverseWords(std::string s) {
int i = 0;
int n = s.length();
string ans;
while (i < n) {
while (i < n && s[i] == ' ') {
i++; // skip spaces
}
if (i >= n) break;
int j = i;
while (j < n && s[j] != ' ') {
j++; // find the end of the word
}
string word = s.substr(i, j - i); // extract the word
if (ans.empty()) {
ans = word; // if it's the first word, no need to add space
} else {
ans = word + " " + ans; // prepend the word
}
i = j; // move to the next word
}
return ans;
}