796. Rotate String
1. Description
We are given two strings, A and B.
A shift on A consists of taking string A and moving the leftmost character to the rightmost position. For example, if A = ‘abcde’, then it will be ‘bcdea’ after one shift on A. Return True if and only if A can become B after some number of shifts on A.
2. Example
Example 1:
Input: A = ‘abcde’, B = ‘cdeab’
Output: true
Example 2:
Input: A = ‘abcde’, B = ‘abced’
Output: false
3. Note
- A and B will have length at most 100.
4. Solutions
My Accepted Solution
n = i_str1.size()
Time complexity: O($n^2$)
Space complexity: O(1)
class Solution
{
private:
bool isMovedStringsEqual(string &i_str1, int startIndex, string &i_str2)
{
for(int i = startIndex, j = 0; j < i_str2.size(); i = (i + 1) % i_str1.size(), j++)
{
if(i_str1[i] != i_str2[j])
return false;
}
return true;
}
public:
// bool rotateString(string A, string B)
bool rotateString(string &i_str1, string &i_str2)
{
if(i_str1.size() != i_str2.size()) return false;
if(i_str1.empty()) return true; // they have the same length
for(int i = 0; i < i_str1.size(); i++)
{
if(isMovedStringsEqual(i_str1, i, i_str2))
return true;
}
return false;
}
};
4.1 Rolling Hash & Rabin–Karp
n = m_str1.size()
Time complexity: O(n)
Space complexity: O(n)
class Solution
{
private:
bool isMovedStringsEqual(string &i_str1, int startIndex, string &i_str2)
{
for(int i = startIndex, j = 0; j < i_str2.size(); i = (i + 1) % i_str1.size(), j++)
{
if(i_str1[i] != i_str2[j])
return false;
}
return true;
}
public:
// bool rotateString(string A, string B)
bool rotateString(string &i_str1, string &i_str2)
{
if(i_str1.size() != i_str2.size()) return false;
if(i_str1.empty()) return true; // they have the same length
for(int i = 0; i < i_str1.size(); i++)
{
if(isMovedStringsEqual(i_str1, i, i_str2))
return true;
}
return false;
}
};