- 设计思想：
-视频讲解链接B站视频讲解
- 复杂度分析：
- 代码：
c++版本:
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 如果是，返回"YES"，反之，返回"NO"。
* @param s1 string字符串
* @param s2 string字符串
* @return string字符串
*/
int getmin(string s) {
// write code here
//i指向最小表示的位置，j作为比较指针
int len = s.size();
int i = 0, j = 1, k = 0, t;
while(i < len && j < len && k < len) {
//如果前后两个字符相同，那么k++;
t = s[(i + k) >= len ? i + k - len : i + k] - s[(j + k) >= len ? j + k - len : j + k];
if(!t) k++;
else{
if(t > 0) i = i + k + 1; //表明前段比后段大 那么前段肯定不能作为前缀
else j = j + k + 1; //后段较大 那么后段就往后 推一下
if(i == j) ++ j; //同一位置的话j移动
k = 0; //每次更新位置要k要从0开始控制
}
}
return (i < j ? i : j)+1;
}
string solve(string s1, string s2) {
// write code here
if(s1.size() != s2.size()){
return "NO";
}
//求出两个字符串的最小表示法
int a = getmin(s1);
int b = getmin(s2);
for(int i = 0;i < s1.size();i ++){
if(s1[(a + i) % s1.size()] != s2[(b + i) % s1.size()]){
return "NO";
}
}
return "YES";
}
};
Java版本：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 如果是，返回"YES"，反之，返回"NO"。
* @param s1 string字符串
* @param s2 string字符串
* @return string字符串
*/
public int getmin (String s) {
// write code here
//i指向最小表示的位置，j作为比较指针
int len = s.length();
int i = 0, j = 1, k = 0, t;
while(i < len && j < len && k < len) {
//如果前后两个字符相同，那么k++;
t = s.charAt((i + k) >= len ? i + k - len : i + k) - s.charAt((j + k) >= len ? j + k - len : j + k);
if(t == 0) k++;
else{
if(t > 0) i = i + k + 1; //表明前段比后段大 那么前段肯定不能作为前缀
else j = j + k + 1; //后段较大 那么后段就往后 推一下
if(i == j) ++ j; //同一位置的话j移动
k = 0; //每次更新位置要k要从0开始控制
}
}
return (i < j ? i : j)+1;
}
public String solve (String s1, String s2) {
// write code here
// write code here
if(s1.length() != s2.length()){
return "NO";
}
//求出两个字符串的最小表示法
int a = getmin(s1);
int b = getmin(s2);
for(int i = 0;i < s1.length();i ++){
if(s1.charAt((a + i) % s1.length()) != s2.charAt((b + i) % s1.length())){
return "NO";
}
}
return "YES";
}
}Python版本:
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 如果是，返回"YES"，反之，返回"NO"。
# @param s1 string字符串
# @param s2 string字符串
# @return string字符串
#
class Solution:
def getmin(self,s):
#i指向最小表示的位置，j作为比较指针
n = len(s);
i,j,k,t = 0,1,0,0
while(i < n and j < n and k < n):
#如果前后两个字符相同，那么k++;
t = ord(s[(i + k - n) if (i + k) >= n else i + k]) - ord(s[j + k - n if (j + k) >= n else j + k])
if(t == 0): k += 1
else:
if(t > 0): i = i + k + 1#表明前段比后段大 那么前段肯定不能作为前缀
else: j = j + k + 1#后段较大 那么后段就往后 推一下
if(i == j): j += 1#同一位置的话j移动
k = 0#每次更新位置要k要从0开始控制
return (i if i < j else j) + 1
def solve(self , s1 , s2 ):
# write code here
if len(s1) != len(s2):return "NO"
#求出两个字符串的最小表示法
a = self.getmin(s1);
b = self.getmin(s2);
for i in range(0,len(s1)):
if s1[(a + i) % len(s1)] != s2[(b+i)%len(s2)]:
return "NO"
return "YES"JavaScript版本:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 如果是，返回"YES"，反之，返回"NO"。
* @param s1 string字符串
* @param s2 string字符串
* @return string字符串
*/
function getmin( s ) {
// write code here
//i指向最小表示的位置，j作为比较指针
let len = s.length;
let i = 0, j = 1, k = 0, t;
while(i < len && j < len && k < len) {
//如果前后两个字符相同，那么k++;
t = s[(i + k) >= len ? i + k - len : i + k].charCodeAt() - s[(j + k) >= len ? j + k - len : j + k].charCodeAt();
if(!t) k++;
else{
if(t > 0) i = i + k + 1; //表明前段比后段大 那么前段肯定不能作为前缀
else j = j + k + 1; //后段较大 那么后段就往后 推一下
if(i == j) ++ j; //同一位置的话j移动
k = 0; //每次更新位置要k要从0开始控制
}
}
return (i < j ? i : j)+1;
}
function solve( s1 , s2 ) {
// write code here
if(s1.length != s2.length){
return "NO";
}
//求出两个字符串的最小表示法
let a = getmin(s1);
let b = getmin(s2);
for(let i = 0;i < s1.length;i ++){
if(s1.charAt((a + i) % s1.length) != s2.charAt((b + i) % s1.length)){
return "NO";
}
}
return "YES";
}
module.exports = {
solve : solve
};
京公网安备 11010502036488号