leetcode/lcci/01.09.String Rotation

comments	difficulty	edit_url
true	Easy	https://github.com/doocs/leetcode/edit/main/lcci/01.09.String%20Rotation/README_EN.md

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.

Python3

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

Java

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

C++

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

Go

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

TypeScript

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

Rust

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

Swift

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