Java?C++題解leetcode字符串輪轉(zhuǎn)KMP算法詳解
更新時間：2022年09月29日 15:51:44 作者：AnjaVon
這篇文章主要為大家介紹了Java?C++題解leetcode字符串輪轉(zhuǎn)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; // 跳轉(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;
}
}
- 時間復雜度：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; // 跳轉(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;
}
};
- 時間復雜度：O(n)
- 空間復雜度：O(n)
調(diào)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)
總結(jié)
做過了輪轉(zhuǎn)的題就能很快意識到拼接然后找子串，本來調(diào)個API結(jié)束結(jié)果發(fā)現(xiàn)了KMP算法，就淺學一下~
時間耗在算法了就掠過rust各種辣~
以上就是Java C++題解leetcode字符串輪轉(zhuǎn)KMP算法詳解的詳細內(nèi)容，更多關于Java C++ 字符串輪轉(zhuǎn)KMP算法的資料請關注腳本之家其它相關文章！
相關文章
java 方法重寫與權(quán)限修飾符以及多態(tài)和抽象類詳解概念和用法
重寫是子類對父類的允許訪問的方法的實現(xiàn)過程進行重新編寫, 返回值和形參都不能改變。即外殼不變，核心重寫，權(quán)限修飾符用于控制被修飾變量、方法、類的可見范圍，說明了面向?qū)ο蟮姆庋b性，所以我們要適用他們盡可能的讓權(quán)限降到最低，從而安全性提高2021-10-10
mybatis連接數(shù)據(jù)庫實現(xiàn)雙表查詢
本文主要介紹了mybatis連接數(shù)據(jù)庫實現(xiàn)雙表查詢,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2024-09-09
SpringBoot實現(xiàn)elasticsearch 查詢操作(RestHighLevelClient
這篇文章主要給大家介紹了SpringBoot如何實現(xiàn)elasticsearch 查詢操作，文中有詳細的代碼示例和操作流程，具有一定的參考價值,需要的朋友可以參考下2023-07-07
這篇文章主要介紹了Java基于redis實現(xiàn)分布式鎖代碼實例,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-04-04
這篇文章主要為大家介紹了spring?boot集成redisson的最佳實踐示例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2022-03-03
spring使用aspect注解切面不起作用的排查過程及解決
這篇文章主要介紹了spring使用aspect注解切面不起作用的排查過程及解決方案，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
下面小編就為大家?guī)硪黄猀uartz之Job與JobDetail深入解析。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-06-06
這篇文章主要介紹了Spring如何基于aop實現(xiàn)操作日志功能,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-11-11
下面小編就為大家?guī)硪黄斦凷pring對IOC的理解(推薦篇)。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-10-10
本文主要介紹了spring用戶通過交互界面登錄成功的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-07-07