Java C++题解leetcode字符串轮转KMP算法详解

题目要求

思路一：双指针（模拟）

Java

class Solution {
   public boolean isFlipedString(String s1, String s2) {
       if (s1.length() != s2.length())
           return false;
       int n = s1.length();
       if (n == 0)
           return true;
       for (int i = 0; i < n; i++) {
           boolean res = true;
           for (int j = 0; j < n; j++) {
               if (s1.charAt((i + j) ％ n) != s2.charAt(j)) {
                   res = false;
                   break;
               }
           }
           if (res)
               return true;
       }
       return false;
   }
}

• 时间复杂度：O(n^2)

• 空间复杂度：O(1)

C++

class Solution {
public:
   bool isFlipedString(string s1, string s2) {
       if (s1.size() != s2.size())
           return false;
       int n = s1.size();
       if (n == 0)
           return true;
       for (int i = 0; i < n; i++) {
           bool res = true;
           for (int j = 0; j < n; j++) {
               if (s1[(i + j) ％ n] != s2[j]) {
                   res = false;
                   break;
               }
           }
           if (res)
               return true;
       }
       return false;
   }
};

• 时间复杂度：O(n^2)

• 空间复杂度：O(1)

思路二：子串

手写KMP

KMP的思路可以参考KMP 算法详解和详解KMP算法

Java

get_next

class Solution {
   public boolean isFlipedString(String s1, String s2) {
       if (s1.length() != s2.length())
           return false;
       int n = s1.length();
       if (n == 0)
           return true;
       int[] nxt = new int[n];
       nxt[0] = -1;
       int j = 0; // pat指针
       int k = -1; // 跳转位置
       while (j &lt; n - 1) {
           if (k == -1 || s2.charAt(j) == s2.charAt(k)) {
               if (s2.charAt(++j) == s2.charAt(++k))
                   nxt[j] = nxt[k]; // 连续相同
               else
                   nxt[j] = k;
           }
           else
               k = nxt[k];
       }
       String txt = s1 + s1;
       j = 0;
       for (int i = 0; i &lt; 2 * n; i++) {
           if (j &lt; n &amp;&amp; txt.charAt(i) == s2.charAt(j))
               j++;
           else {
               j = nxt[j];
               if (j == -1)
                   j++;
           }
           if (j == n)
               return true;
       }
       return false;
   }
}

dp

class Solution {
   public boolean isFlipedString(String s1, String s2) {
       if (s1.length() != s2.length())
           return false;
       int n = s1.length();
       if (n == 0)
           return true;
       int[][] dp = new int[n][256]; // dp[state][char] = nxt state
       dp[0][s2.charAt(0)] = 1;
       int x = 0; // 影子状态
       for (int s = 1; s < n; s++) {
           for (int c = 0; c < 256; c++)
               dp[s][c] = dp[x][c];
           dp[s][s2.charAt(s)] = s + 1;
           x = dp[x][s2.charAt(s)];
       }
       String txt = s1 + s1;
       int state = 0;
       for (int i = 0; i < 2 * n; i++) {
           state = dp[state][txt.charAt(i)];
           if (state == n)
               return true;
       }
       return false;
   }
}

• 时间复杂度：O(n)

• 空间复杂度：O(n)

C++

get_next

class Solution {
public:
   bool isFlipedString(string s1, string s2) {
       if (s1.size() != s2.size())
           return false;
       int n = s1.size();
       if (n == 0)
           return true;
       int nxt[n];
       nxt[0] = -1;
       int j = 0; // pat指针
       int k = -1; // 跳转位置
       while (j < n - 1) {
           if (k == -1 || s2[j] == s2[k]) {
               if (s2[++j] == s2[++k])
                   nxt[j] = nxt[k]; // 连续相同
               else
                   nxt[j] = k;
           }
           else
               k = nxt[k];
       }
       string txt = s1 + s1;
       j = 0;
       for (int i = 0; i < 2 * n; i++) {
           if (j < n && txt[i] == s2[j])
               j++;
           else {
               j = nxt[j];
               if (j == -1)
                   j++;
           }
           if (j == n)
               return true;
       }
       return false;
   }
};

dp

class Solution {
public:
   bool isFlipedString(string s1, string s2) {
       if (s1.size() != s2.size())
           return false;
       int n = s1.size();
       if (n == 0)
           return true;
       int dp[n][256]; // dp[state][char] = nxt state
       memset(dp, 0, sizeof(dp));
       dp[0][s2[0]] = 1;
       int x = 0; // 影子状态
       for (int s = 1; s < n; s++) {
           for (int c = 0; c < 256; c++)
               dp[s][c] = dp[x][c];
           dp[s][s2[s]] = s + 1;
           x = dp[x][s2[s]];
       }
       string txt = s1 + s1;
       int state = 0;
       for (int i = 0; i < 2 * n; i++) {
           state = dp[state][txt[i]];
           if (state == n)
               return true;
       }
       return false;
   }
};

• 时间复杂度：O(n)

• 空间复杂度：O(n)

调API

Java

class Solution {
   public boolean isFlipedString(String s1, String s2) {
       return s1.length() == s2.length() && (s1 + s1).contains(s2);
   }
}

• 时间复杂度：O(n)，取决于语言匹配子字符串机制

• 空间复杂度：O(n)

C++

class Solution {
public:
   bool isFlipedString(string s1, string s2) {
       return s1.size() == s2.size() && (s1 + s1).find(s2) != string::npos;
   }
};

• 时间复杂度：O(n)，取决于语言匹配子字符串机制

• 空间复杂度：O(n)

impl Solution {
   pub fn is_fliped_string(s1: String, s2: String) -> bool {
       s1.len() == s2.len() && s2.repeat(2).contains(&s1)
   }
}

• 时间复杂度：O(n)，取决于语言匹配子字符串机制

• 空间复杂度：O(n)

来源：https://juejin.cn/post/7148653822250844173