Skip to content

01.09. String Rotation

Description

Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 (e.g.,"waterbottle" is a rotation of"erbottlewat"). Can you use only one call to the method that checks if one word is a substring of another?

Example 1:

Input: s1 = "waterbottle", s2 = "erbottlewat"

Output: True

Example 2:

Input: s1 = "aa", "aba"

Output: False

 

Note:

  1. 0 <= s1.length, s1.length <= 100000

Solutions

Solution 1: String Matching

Thinking

A rotation moves a prefix to the end. Trying every cut is \(n\) comparisons of length \(n\), acceptable but redundant.

Unequal lengths cannot be rotations. When lengths match, \(s_1+s_1\) contains every rotation of \(s_1\), so the question is whether \(s_2\) is a substring of that concatenation.

The code compares lengths first, then uses s2 in s1 * 2, which is exactly that test.

First, if the lengths of strings \(s1\) and \(s2\) are not equal, they are definitely not rotation strings of each other.

Second, if the lengths of strings \(s1\) and \(s2\) are equal, then by concatenating two \(s1\) together, the resulting string \(s1 + s1\) will definitely include all rotation cases of \(s1\). At this point, we just need to check whether \(s2\) is a substring of \(s1 + s1\).

# True
s1 = "aba"
s2 = "baa"
s1 + s1 = "abaaba"
            ^^^

# False
s1 = "aba"
s2 = "bab"
s1 + s1 = "abaaba"

The time complexity is \(O(n)\), and the space complexity is \(O(n)\). Here, \(n\) is the length of string \(s1\).

1
2
3
class Solution:
    def isFlipedString(self, s1: str, s2: str) -> bool:
        return len(s1) == len(s2) and s2 in s1 * 2

1
2
3
4
5
class Solution {
    public boolean isFlipedString(String s1, String s2) {
        return s1.length() == s2.length() && (s1 + s1).contains(s2);
    }
}

1
2
3
4
5
6
class Solution {
public:
    bool isFlipedString(string s1, string s2) {
        return s1.size() == s2.size() && (s1 + s1).find(s2) != string::npos;
    }
};

1
2
3
func isFlipedString(s1 string, s2 string) bool {
    return len(s1) == len(s2) && strings.Contains(s1+s1, s2)
}

1
2
3
function isFlipedString(s1: string, s2: string): boolean {
    return s1.length === s2.length && (s2 + s2).indexOf(s1) !== -1;
}

1
2
3
4
5
impl Solution {
    pub fn is_fliped_string(s1: String, s2: String) -> bool {
        s1.len() == s2.len() && (s2.clone() + &s2).contains(&s1)
    }
}

1
2
3
4
5
class Solution {
    func isFlippedString(_ s1: String, _ s2: String) -> Bool {
        return (s1.isEmpty && s2.isEmpty) || (s1.count == s2.count && (s1 + s1).contains(s2))
    }
}

Comments