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$.

Python3JavaC++GoTypeScriptRustSwift

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

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

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

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

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

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

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

Comments