@@techdose4u why do we need partitions for the 1st method? we can simply find original string 1st char position in 2nd string (say K), then we can use rotation logic on the original string for k. O(N)
if(str1.length() != str2.length()) return false; Add this in the code as for the test case -- coder and code , it will return true which is not correct
lass Solution { public: //Function to check if two strings are rotations of each other or not. bool areRotations(string s1,string s2) { if(s1.size()!= s2.size())return 0; for(int i=0;i
i think the time complexity for the first approach should be O(n^3) because we are doing nothing but generating all possible left rotations of the given array(which takes O(n^2) TC and at each stage we are comparing the rotated string with the goal string so the time complexity should be O(n^3). Correct me if i am wrong
precisely it it O(n*(n+n)) which is O(2n^2). Why? It is because the outer loop is going for 1 to n rotation and inside the loop the rotation is taking place which is O(n) and after the rotation we are checking equality which is another O(n).
second method is not KMP algorithm. Second method also has a time complexity of O(N^2). Take example of S1="aaaaaab" and s2="aaaabaa" now s1+s1 = "aaaaaabaaaaaab". Now when you try to search for s2 in modified s1. For every first occurrence of a you search till a character is mismatched so in worst case it takes O(N^2) time. Please do not give wrong information to students. Do some proper research before you make a video
@@choyeshmohanty8731 I think its necessary that the person who makes the video should be sure whether he is teaching the right algorithm or not. Otherwise whats the point of making videos? A lot of students follow this channel so its better to avoid these kind of mistakes
I solve this problem in a much simpler way. Correct me if I am wrong. So I know if a string is a rotation of another string then their length must me equivalent. but we need to go further than that because just having the same length is not sufficient. Secondly, I know the characters are and must be the exact same in both strings just not in the same order/arrangement. So what I can do, I can sort string s2 and then sort string s1 and traverse both strings with a nested for loop to verify if all characters at each index is the same. It it is true then string s2 must have been a rotation of string s1. Let me know what you think about that solution. I know it's space complexity is not that great but it's time complexity is pretty solid. Let me know if I got it all wrong. I coded it and here is the code below. #include #include using namespace std; bool isSubstring (string s1, string s2){ int n1 = s1.length(); int n2 = s2.length(); if (n1 == n2) return true; sort(s1.begin(), s1.end()); sort (s2.begin(), s2.end()); for (int i = 0; i < n1; i++) for (int j = 0; j < i; j++) if (s1[i] != s2[j]) return false; return 0; } int main() { string s1 = "waterbottle"; string s2 = "erbottlewat"; if (isSubstring(s1, s2)){ cout
i think it will be wrong since ur code return true for MYPENCIL AND ENCILMYP AND MYPENCIL AND ENCILMPY ASLO. u r not checking the order of the string in ur code
class Solution: def rotateString(self, s: str, goal: str) -> bool: if len(s) != len(goal): return False if s == goal: return True for i in range(1, len(s)): s = s[1:] + s[0] if s == goal: return True return False
This is my take: O(n) complexity public class RotationOfString { //Option + Command + l --> to Format in intelliJ public static boolean checkRotation(String a, String b) { int index = 0; for (int i = 0; i < a.length(); i++) if (b.charAt(i) == a.charAt(0)) { index = i; break; } for (int i = 0; i < a.length(); i++) { if (index > a.length() - 1) index -= a.length(); if (a.charAt(i) != b.charAt(index)) { return false; } else index = index + 1; } return true; } public static void main(String[] args) { System.out.println("Output ::" + checkRotation("AADHARSH", "HAADHARS")); } }
This is one of the best approach I saw today! Awesome awesome! I was like OMG, had never thought about KMP could come handy here! Great!
:)
@@techdose4u why do we need partitions for the 1st method? we can simply find original string 1st char position in 2nd string (say K), then we can use rotation logic on the original string for k. O(N)
@@04tridib But that logic fails as the string may contain duplicates characters.
No one explains better than TECH DOSE......THANKS
Welcome
job lgi?
The KMP is one of the simplest and best approach I have found till :). Thank you for your contribution.
You are welcome!
bool areRotations(string str1,string str2)
{
string temp= str1+str1;
int find=temp.find(str2);
if(find>=0)
{
return true;
}
return false;
}
thanx for the code bro
if(str1.length() != str2.length())
return false;
Add this in the code as for the test case -- coder
and code , it will return true which is not correct
Bro u did not use kmp to match the strings.
It left me saying a "WOW" wide out loud!!
Thank you for this amazing explanation.
Welcome :)
NICE SUPER EXCELLENT MOTIVATED
Nice :)
Thankyou so much for your explanation....and that algorithm was fantastic...within few lines the question got solved
Welcome :)
impoving hand writing will be very helpful for this channel. best.
Thanks :) I am trying that in my recent videos
nyc one
i like ur way of explanation.
thnk u
Welcome
very detailed explanation thanks bhai :)
Welcome
class Solution {
public:
bool rotateString(string s, string goal) {
if(s.length()!=goal.length()){
return false;
}
string res=s+s;
for(int i=0;i
Thanks very nice explanation
class Solution {
public boolean rotateString(String s, String goal) {
if(s.length()!=goal.length())
return false;
if(s.equals(goal))
return true;
for(int i=1;i
lass Solution
{
public:
//Function to check if two strings are rotations of each other or not.
bool areRotations(string s1,string s2)
{ if(s1.size()!= s2.size())return 0;
for(int i=0;i
You should have knew till now, that comparing two strings and calling substr aren't constant time
relational comparision of string in worst case is o(n) itself so overall o(n*n)
Can you show this video as an code in c
I know this one is not optimal but better than n^2 how about sorting both s1 and s2 then checking both are equal or not it would take O(nlogn)
No it will not work.Bcoz if you sort the strings whats the point of rotations.
@@gogamers3333 yeah true idk what i was thinking at that moment.
thanks
Good one
For solution 1
I guess my solution works in O(N)
class Solution
{
public static boolean check(String X, String Y)
{
// Write your code here...
if(X.length() == Y.length()){
if (X.equals(Y)) {
return true;
}
int partition=1;
for(int i=partition;i
you are doing .equals method inside for loop. I guess it is still greater than O(n)
substring takes o(n)
i think the time complexity for the first approach should be O(n^3) because we are doing nothing but generating all possible left rotations of the given array(which takes O(n^2) TC and at each stage we are comparing the rotated string with the goal string so the time complexity should be O(n^3).
Correct me if i am wrong
I also think the time complexity of first method is O(n^3)
precisely it it O(n*(n+n)) which is O(2n^2). Why? It is because the outer loop is going for 1 to n rotation and inside the loop the rotation is taking place which is O(n) and after the rotation we are checking equality which is another O(n).
The second method is not KMP algorithm I guess.
Its not KMP algo
Plz introduce your self .. in one video ..about yourself and education ...anyway your content is excellent ..but it take time to grow your channel
Thanks for your motivation :) If you wanna know more about me: www.linkedin.com/in/surya-pratap-kahar-47bb01168
can somebody share the solution for first approach
public static boolean check(String str1,String str2)
{
if(str1.length()!=str2.length())
return false;
if(str1.equals(str2))
return true;
for(int i=0;i
method does not pass every testcase
second method is not KMP algorithm. Second method also has a time complexity of O(N^2). Take example of S1="aaaaaab" and s2="aaaabaa" now s1+s1 = "aaaaaabaaaaaab". Now when you try to search for s2 in modified s1. For every first occurrence of a you search till a character is mismatched so in worst case it takes O(N^2) time. Please do not give wrong information to students. Do some proper research before you make a video
This video has been made 2 years ago...if you are think this is optimal its okay...but don't give advise while writing comments to teacher...
@@choyeshmohanty8731 I think its necessary that the person who makes the video should be sure whether he is teaching the right algorithm or not. Otherwise whats the point of making videos? A lot of students follow this channel so its better to avoid these kind of mistakes
@@shravani2922, I agree. TC for the second approach would still be O(n2).
It's not kmp algorithm
@@shravani2922 thanks mann that's what i was thinking that 2nd approach is even worse cause it has same TC and even worst SC
I solve this problem in a much simpler way. Correct me if I am wrong. So I know if a string is a rotation of another string then their length must me equivalent. but we need to go further than that because just having the same length is not sufficient. Secondly, I know the characters are and must be the exact same in both strings just not in the same order/arrangement. So what I can do, I can sort string s2 and then sort string s1 and traverse both strings with a nested for loop to verify if all characters at each index is the same. It it is true then string s2 must have been a rotation of string s1. Let me know what you think about that solution. I know it's space complexity is not that great but it's time complexity is pretty solid. Let me know if I got it all wrong. I coded it and here is the code below.
#include
#include
using namespace std;
bool isSubstring (string s1, string s2){
int n1 = s1.length();
int n2 = s2.length();
if (n1 == n2)
return true;
sort(s1.begin(), s1.end());
sort (s2.begin(), s2.end());
for (int i = 0; i < n1; i++)
for (int j = 0; j < i; j++)
if (s1[i] != s2[j])
return false;
return 0;
}
int main() {
string s1 = "waterbottle";
string s2 = "erbottlewat";
if (isSubstring(s1, s2)){
cout
i think it will be wrong
since ur code return true for MYPENCIL AND ENCILMYP
AND
MYPENCIL AND ENCILMPY ASLO.
u r not checking the order of the string in ur code
class Solution:
def rotateString(self, s: str, goal: str) -> bool:
if len(s) != len(goal):
return False
if s == goal:
return True
for i in range(1, len(s)):
s = s[1:] + s[0]
if s == goal:
return True
return False
o(n^2)
O(n)
@@shristisingh169 the slicing operation takes internally O(n)
@@SharuxD you mean comparison of two strings na??
This is my take: O(n) complexity
public class RotationOfString {
//Option + Command + l --> to Format in intelliJ
public static boolean checkRotation(String a, String b) {
int index = 0;
for (int i = 0; i < a.length(); i++)
if (b.charAt(i) == a.charAt(0)) {
index = i;
break;
}
for (int i = 0; i < a.length(); i++) {
if (index > a.length() - 1) index -= a.length();
if (a.charAt(i) != b.charAt(index)) {
return false;
} else index = index + 1;
}
return true;
}
public static void main(String[] args) {
System.out.println("Output ::" + checkRotation("AADHARSH", "HAADHARS"));
}
}