字符串轮转
难度:
标签:
题目描述
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", s2 = "aba" Output: False
Note:
0 <= s1.length, s2.length <= 100000
代码结果
运行时间: 19 ms, 内存: 16.3 MB
/*
题目思路：
同样的思路，我们通过拼接s1自身来创建一个新的字符串temp，并检查s2是否是temp的子串。
在Java Stream中，我们没有直接的stream支持contains的操作，因此这里的代码和普通Java代码类似，只是代码结构会有所不同。
*/
import java.util.stream.Stream;
public class Solution {
public boolean isRotation(String s1, String s2) {
if (s1.length() != s2.length()) {
return false;
}
String temp = Stream.of(s1, s1).reduce("", String::concat);
return temp.contains(s2);
}
}解释
方法:
解题思路是基于一个简单的观察：如果字符串s2是字符串s1的一个轮转，那么s2必然是由s1两部分的某种组合（前半段和后半段）构成的。因此，如果我们将s1与自身拼接，形成新字符串s1s1，那么s2必须是s1s1的一个子字符串。这种方法首先检查两个字符串长度是否相等，若不相等，则s2不可能是s1的轮转。如果长度相等，再检查s2是否为s1s1的子串。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在解题思路中，你提到如果s2是s1的轮转，s2必然是s1s1的子字符串。这一结论是怎样得出的？
▷🦆
题解中提到首先检查s1和s2的长度是否相等，这一步是否足够保证s2能通过后续的子串检查步骤？
▷🦆
在题解的代码实现中，检查s2是否为新字符串s1s1的子串时使用了`(s2 + s2)`，这似乎是一个笔误。正确的表达应该是什么？
▷