- 设计思想:
-视频讲解链接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 };