当前位置: 面试刷题>> 旋转字符串 (经典算法题500道)


题目描述

题目:旋转字符串

给定两个字符串s1s2,请编写一个函数来判断s2是否为s1旋转后的字符串。也就是说,你可以把字符串s1连接其自身,形成一个新的字符串,然后检查s2是否为这个新字符串的子串。

示例

  • 输入:s1 = "waterbottle", s2 = "erbottlewat"

  • 输出:true

  • 解释:将s1连接自身得到"waterbottlewaterbottle",从中可以找到子串"erbottlewat",因此返回true

  • 输入:s1 = "abc", s2 = "cab"

  • 输出:true

  • 解释:将s1连接自身得到"abcabc",从中可以找到子串"cab",因此返回true

  • 输入:s1 = "abcde", s2 = "abced"

  • 输出:false

  • 解释:将s1连接自身后,找不到与s2完全相同的子串。

PHP 示例代码

function isRotate($s1, $s2) {
    if (strlen($s1) != strlen($s2)) {
        return false;
    }
    
    $s1s1 = $s1 . $s1; // 连接s1自身
    return strpos($s1s1, $s2) !== false; // 检查s2是否为s1s1的子串
}

// 示例
echo isRotate("waterbottle", "erbottlewat") ? "true" : "false"; // 输出 true
echo isRotate("abc", "cab") ? "true" : "false"; // 输出 true
echo isRotate("abcde", "abced") ? "true" : "false"; // 输出 false

Python 示例代码

def is_rotate(s1, s2):
    if len(s1) != len(s2):
        return False
    
    s1s1 = s1 + s1
    return s2 in s1s1

# 示例
print(is_rotate("waterbottle", "erbottlewat")) # 输出 True
print(is_rotate("abc", "cab")) # 输出 True
print(is_rotate("abcde", "abced")) # 输出 False

JavaScript 示例代码

function isRotate(s1, s2) {
    if (s1.length !== s2.length) {
        return false;
    }
    
    const s1s1 = s1 + s1;
    return s1s1.includes(s2);
}

// 示例
console.log(isRotate("waterbottle", "erbottlewat")); // 输出 true
console.log(isRotate("abc", "cab")); // 输出 true
console.log(isRotate("abcde", "abced")); // 输出 false

注意: 在这些示例代码中,我们检查了s1s2的长度是否相等,因为如果长度不等,s2绝对不可能是s1旋转后的字符串。然后,我们创建了s1的重复字符串s1s1,并检查s2是否为s1s1的子串。这种方法的时间复杂度主要由字符串连接和子串查找操作决定,但在大多数情况下是高效的。

推荐面试题