跳转至

面试题 01.09. 字符串轮转

题目描述

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

示例1:

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

示例2:

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

提示：

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

说明:

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

解法

方法一：字符串匹配

思考

旋转即把某前缀挪到末尾。枚举所有切割点再比较，共 \(n\) 次、每次 \(O(n)\)，在长度相等时可行，但重复比较较多。

长度不等则必不是旋转。长度相等时，\(s_1+s_1\) 覆盖 \(s_1\) 的全部旋转，于是问题化为一次子串判定：\(s_2\) 是否出现在 \(s_1+s_1\) 中。

代码先比长度，再用 s2 in s1 * 2 完成包含检查，与上述观察一致。

首先，如果字符串 \(s1\) 和 \(s2\) 长度不相等，那么肯定不是旋转字符串。

其次，如果字符串 \(s1\) 和 \(s2\) 长度相等，那么将两个 \(s1\) 连接，得到的 \(s1 + s1\) 这个字符串一定包含了 \(s1\) 旋转的所有情况，这时候我们只要判断 \(s2\) 是否是 \(s1 + s1\) 的子串即可。

# 成立
s1 = "aba"
s2 = "baa"
s1 + s1 = "abaaba"
            ^^^

# 不成立
s1 = "aba"
s2 = "bab"
s1 + s1 = "abaaba"

时间复杂度 \(O(n)\)，空间复杂度 \(O(n)\)。其中 \(n\) 为字符串 \(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))
    }
}

评论