Java?C++題解leetcode字符串輪轉(zhuǎn)KMP算法詳解
更新時(shí)間：2022年09月29日 15:51:44 作者：AnjaVon
這篇文章主要為大家介紹了Java?C++題解leetcode字符串輪轉(zhuǎn)KMP算法詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪
題目要求
思路一：雙指針（模擬）
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;
}
}
- 時(shí)間復(fù)雜度：O(n^2)
- 空間復(fù)雜度：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;
}
};
- 時(shí)間復(fù)雜度：O(n^2)
- 空間復(fù)雜度：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; // 跳轉(zhuǎn)位置
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;
}
}
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：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; // 跳轉(zhuǎn)位置
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;
}
};
- 時(shí)間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n)
調(diào)API
Java
class Solution {
public boolean isFlipedString(String s1, String s2) {
return s1.length() == s2.length() && (s1 + s1).contains(s2);
}
}
- 時(shí)間復(fù)雜度：O(n)，取決于語(yǔ)言匹配子字符串機(jī)制
- 空間復(fù)雜度：O(n)
C++
class Solution {
public:
bool isFlipedString(string s1, string s2) {
return s1.size() == s2.size() && (s1 + s1).find(s2) != string::npos;
}
};
- 時(shí)間復(fù)雜度：O(n)，取決于語(yǔ)言匹配子字符串機(jī)制
- 空間復(fù)雜度：O(n)
impl Solution {
pub fn is_fliped_string(s1: String, s2: String) -> bool {
s1.len() == s2.len() && s2.repeat(2).contains(&s1)
}
}
- 時(shí)間復(fù)雜度：O(n)，取決于語(yǔ)言匹配子字符串機(jī)制
- 空間復(fù)雜度：O(n)
總結(jié)
做過了輪轉(zhuǎn)的題就能很快意識(shí)到拼接然后找子串，本來(lái)調(diào)個(gè)API結(jié)束結(jié)果發(fā)現(xiàn)了KMP算法，就淺學(xué)一下~
時(shí)間耗在算法了就掠過rust各種辣~
以上就是Java C++題解leetcode字符串輪轉(zhuǎn)KMP算法詳解的詳細(xì)內(nèi)容，更多關(guān)于Java C++ 字符串輪轉(zhuǎn)KMP算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！
您可能感興趣的文章:
- C C++算法題解LeetCode1408數(shù)組中的字符串匹配
- Java?C++算法題解leetcode801使序列遞增的最小交換次數(shù)
- Java C++算法題解leetcode1592重新排列單詞間的空格
- Java C++ 算法題解leetcode1582二進(jìn)制矩陣特殊位置
- Java?C++?算法題解leetcode145商品折扣后最終價(jià)格單調(diào)棧
- Java C++ 算法leetcode828統(tǒng)計(jì)子串中唯一字符乘法原理
- Java?C++?算法題解leetcode669修剪二叉搜索樹示例
- c++算法進(jìn)階刪除有序鏈表中的重復(fù)元素
相關(guān)文章
Java中HashMap與String字符串互轉(zhuǎn)的問題解決
本文介紹了Java中HashMap與String字符串互轉(zhuǎn)的問題解決，當(dāng)我們有需求將HashMap轉(zhuǎn)為Json格式的String時(shí)，需要使用FastJson/Gson將HashMap轉(zhuǎn)為String，感興趣的可以了解一下2022-03-03
springboot如何使用assembly打包項(xiàng)目和啟動(dòng)腳本
這篇文章主要介紹了springboot如何使用assembly打包項(xiàng)目和啟動(dòng)腳本問題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2023-06-06
Springdoc替換swagger的實(shí)現(xiàn)步驟分解
最近在spring看到的，spring要對(duì)api文檔動(dòng)手了，有些人說swagger不好用，其實(shí)也沒那么不好用，有人說代碼還是有點(diǎn)侵入性，這倒是真的，我剛試了springdoc可以說還是有侵入性但是也可以沒有侵入性，這就看你對(duì)文檔有什么要求了2023-02-02
spring mvc DispatcherServlet之前端控制器架構(gòu)詳解
這篇文章主要為大家詳細(xì)介紹了spring mvc DispatcherServlet之前端控制器架構(gòu)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-04-04
Java實(shí)現(xiàn)HashMap排序方法的示例詳解
這篇文章主要通過一些示例為大家介紹了Java對(duì)HashMap進(jìn)行排序的方法，幫助大家更好的理解和使用Java，感興趣的朋友可以了解一下2022-05-05
springboot集成redis啟動(dòng)報(bào)錯(cuò)問題的解決方式
這篇文章主要介紹了springboot集成redis啟動(dòng)報(bào)錯(cuò)問題的解決方式,從錯(cuò)誤信息上看缺少pool2相關(guān)包,查詢資料發(fā)現(xiàn)當(dāng)redis客戶端選擇Lettuce時(shí)候需要增加：commons-pool22023-11-11
添加引用,重啟服務(wù),需要的朋友可以參考下
使用IDEA向Gitee提交SpringBoot項(xiàng)目進(jìn)行遠(yuǎn)程管理
本文主要介紹了使用IDEA向Gitee提交SpringBoot項(xiàng)目進(jìn)行遠(yuǎn)程管理，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-01-01
使用EasyPoi實(shí)現(xiàn)多Sheet頁(yè)導(dǎo)出的示例代碼
在項(xiàng)目開發(fā)中,我們常常會(huì)遇到導(dǎo)出多Sheet頁(yè)的需求,本文降維打擊介紹一下如何使用EasyPoi實(shí)現(xiàn)這一功能,文中的示例代碼簡(jiǎn)潔易懂,有需要的可以參考下2025-03-03
今天給大家?guī)?lái)的是關(guān)于Java的相關(guān)知識(shí),文章圍繞著Java加密算法展開,文中有非常詳細(xì)的介紹及代碼示例,需要的朋友可以參考下2021-06-06
IntelliJ?IDEA?代碼運(yùn)行時(shí)中文出現(xiàn)亂碼問題及解決方法
在我們剛接觸到IDEA時(shí)，想美滋滋的敲一個(gè)“hello?world”來(lái)問候這個(gè)世界，但難免會(huì)遇到這種問題亂碼，這篇文章主要介紹了解決IntelliJ?IDEA?代碼運(yùn)行時(shí)中文出現(xiàn)亂碼問題,需要的朋友可以參考下2023-09-09