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