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

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