Java?C++題解leetcode字符串輪轉KMP算法詳解
更新時間：2022年09月29日 15:51:44 作者：AnjaVon
這篇文章主要為大家介紹了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
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 < n - 1) {
if (k == -1 || s2.charAt(j) == s2.charAt(k)) {
if (s2.charAt(++j) == s2.charAt(++k))
nxt[j] = nxt[k]; // 連續(xù)相同
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.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; // 影子狀態(tài)
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]; // 連續(xù)相同
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; // 影子狀態(tài)
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)
總結
做過了輪轉的題就能很快意識到拼接然后找子串，本來調個API結束結果發(fā)現(xiàn)了KMP算法，就淺學一下~
時間耗在算法了就掠過rust各種辣~
以上就是Java C++題解leetcode字符串輪轉KMP算法詳解的詳細內容，更多關于Java C++ 字符串輪轉KMP算法的資料請關注腳本之家其它相關文章！
相關文章
本文介紹了Java中HashMap與String字符串互轉的問題解決，當我們有需求將HashMap轉為Json格式的String時，需要使用FastJson/Gson將HashMap轉為String，感興趣的可以了解一下2022-03-03
springboot如何使用assembly打包項目和啟動腳本
這篇文章主要介紹了springboot如何使用assembly打包項目和啟動腳本問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-06-06
Springdoc替換swagger的實現(xiàn)步驟分解
最近在spring看到的，spring要對api文檔動手了，有些人說swagger不好用，其實也沒那么不好用，有人說代碼還是有點侵入性，這倒是真的，我剛試了springdoc可以說還是有侵入性但是也可以沒有侵入性，這就看你對文檔有什么要求了2023-02-02
spring mvc DispatcherServlet之前端控制器架構詳解
這篇文章主要為大家詳細介紹了spring mvc DispatcherServlet之前端控制器架構，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-04-04
這篇文章主要通過一些示例為大家介紹了Java對HashMap進行排序的方法，幫助大家更好的理解和使用Java，感興趣的朋友可以了解一下2022-05-05
這篇文章主要介紹了springboot集成redis啟動報錯問題的解決方式,從錯誤信息上看缺少pool2相關包,查詢資料發(fā)現(xiàn)當redis客戶端選擇Lettuce時候需要增加：commons-pool22023-11-11
添加引用,重啟服務,需要的朋友可以參考下
使用IDEA向Gitee提交SpringBoot項目進行遠程管理
本文主要介紹了使用IDEA向Gitee提交SpringBoot項目進行遠程管理，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-01-01
使用EasyPoi實現(xiàn)多Sheet頁導出的示例代碼
在項目開發(fā)中,我們常常會遇到導出多Sheet頁的需求,本文降維打擊介紹一下如何使用EasyPoi實現(xiàn)這一功能,文中的示例代碼簡潔易懂,有需要的可以參考下2025-03-03
今天給大家?guī)淼氖顷P于Java的相關知識,文章圍繞著Java加密算法展開,文中有非常詳細的介紹及代碼示例,需要的朋友可以參考下2021-06-06
IntelliJ?IDEA?代碼運行時中文出現(xiàn)亂碼問題及解決方法
在我們剛接觸到IDEA時，想美滋滋的敲一個“hello?world”來問候這個世界，但難免會遇到這種問題亂碼，這篇文章主要介紹了解決IntelliJ?IDEA?代碼運行時中文出現(xiàn)亂碼問題,需要的朋友可以參考下2023-09-09