- 题目描述:
图片说明
- 题目链接:
https://www.nowcoder.com/practice/201d6cea532b47d7a203bebc9052f6d5?tpId=196&&tqId=37709&rp=1&ru=/ta/job-code-total&qru=/ta/job-code-total/question-ranking

- 设计思想:

图片说明

-视频讲解链接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
};