面试题 01.09. 字符串轮转

English Version

题目描述

字符串轮转。给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成（比如，waterbottle是erbottlewat旋转后的字符串）。

示例1:

 输入：s1 = "waterbottle", s2 = "erbottlewat"
 输出：True

示例2:

 输入：s1 = "aa", "aba"
 输出：False

提示：

1. 字符串长度在[0, 100000]范围内。

说明:

1. 你能只调用一次检查子串的方法吗？

解法

字符串只是旋转的，将前后拼接起来，就能得到一个包含旋转前字符串在内的新字符串。如：

# 成立
s1 = "aba"
s2 = "baa"
s3 = "baabaa" = s2 + s2
        ^^^

# 不成立
s1 = "aba"
s2 = "bab"
s3 = "babbab" = s2 + s2

Python3

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

Java

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

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)
    }
}

原始写法：

impl Solution {
    pub fn is_fliped_string(s1: String, s2: String) -> bool {
        if s1 == s2 {
            return true;
        }
        if s1.len() != s2.len() {
            return false;
        }
        let s2: Vec<char> = (s2.clone() + &s2).chars().collect();
        let n = s1.len();
        let m = s2.len();
        for i in 0..m - n {
            let mut is_pass = true;
            for (j, c) in s1.chars().enumerate() {
                if c != s2[i + j] {
                    is_pass = false;
                    break;
                }
            }
            if is_pass {
                return true;
            };
        }
        false
    }
}

...