🙋大家好！我是毛毛張!
🌈個人首頁： 神馬都會億點點的毛毛張

🕹?KMP算法練習(xí)題

---

LeetCode鏈接：796. 旋轉(zhuǎn)字符串

---

1.題目描述🍑

給定兩個字符串, s 和 goal。如果在若干次旋轉(zhuǎn)操作之后，s 能變成 goal ，那么返回 true 。

s 的 旋轉(zhuǎn)操作 就是將 s 最左邊的字符移動到最右邊。

• 例如, 若 s = 'abcde'，在旋轉(zhuǎn)一次之后結(jié)果就是'bcdea' 。

示例 1:

輸入: s = "abcde", goal = "cdeab"
輸出: true

示例 2:

輸入: s = "abcde", goal = "abced"
輸出: false

提示:

• 1 <= s.length, goal.length <= 100
• s 和 goal 由小寫英文字母組成

2.題解🫐

2.1 暴力解法🫒

class Solution {public boolean rotateString(String s, String goal) {// 檢查兩個字符串的長度，如果長度不同，返回 falseif (s.length() != goal.length()) return false;char[] chs = s.toCharArray();// 將字符串 s 轉(zhuǎn)換為字符數(shù)組char[] cht = goal.toCharArray();// 將目標字符串 goal 轉(zhuǎn)換為字符數(shù)組// 遍歷每一個可能的旋轉(zhuǎn)位置for (int i = 0; i < chs.length; i++) {// 保存當前字符，以便進行旋轉(zhuǎn)char temp = chs[0];// 將字符數(shù)組向左旋轉(zhuǎn)一位for (int j = 0; j < cht.length - 1; j++) {chs[j] = chs[j + 1];}// 將保存的字符放到數(shù)組末尾chs[chs.length - 1] = temp;// 如果當前旋轉(zhuǎn)后的字符數(shù)組等于目標字符數(shù)組，返回 trueif (Arrays.equals(chs, cht)) return true;}return false;// 如果沒有找到任何匹配，返回 false}
}

2.2 模擬🥭

• 上面我們是通過將字符串轉(zhuǎn)換成字符數(shù)組，然后實際進行旋轉(zhuǎn)，當時實際上并不需要，我們可以通過取模的方式來模擬旋轉(zhuǎn)字符串，這種方法稱為模擬
• 首先，如果$s$和$goal$的長度不一樣，那么無論怎么旋轉(zhuǎn)，$s$都不能得到$goal$，返回$false$。在長度一樣（都為 n）的前提下，假設(shè)$s$旋轉(zhuǎn)$i$位，則與$goal$中的某一位字符$ goal[j] $對應(yīng)的原$s$中的字符應(yīng)該為 $s[(i+j)modn]$。在固定$i$的情況下，遍歷所有$j$，若對應(yīng)字符都相同，則返回$true$。否則，繼續(xù)遍歷其他候選的 $i$。若所有的$i$都不能使$s$變成$goal$，則返回 $false$

class Solution {public boolean rotateString(String s, String goal) {// 檢查兩個字符串的長度，如果不相等則返回 falseif (s.length() != goal.length()) return false;int len = s.length(); // 獲取字符串 s 的長度// 遍歷字符串 s 的每一個字符作為旋轉(zhuǎn)的起始位置for (int i = 0; i < len; i++) {int j; // 初始化目標字符串 goal 的索引// 遍歷目標字符串 goalfor (j = 0; j < len; j++) {// 通過模運算計算旋轉(zhuǎn)后的字符在字符串 s 中的位置，并進行比較if (s.charAt((i + j) % len) != goal.charAt(j)) break; // 如果不匹配，跳出內(nèi)層循環(huán)}// 如果 j 達到目標字符串的長度，表示完全匹配，返回 trueif (j == len) return true;}// 如果沒有找到匹配，返回 falsereturn false;}
}

2.3 字符串匹配 - 移動匹配🥑

• 首先，如果 s 和 goal 的長度不一樣，那么無論怎么旋轉(zhuǎn)，s 都不能得到 goal，返回 false。字符串 s+s 包含了所有 s 可以通過旋轉(zhuǎn)操作得到的字符串，只需要檢查 goal 是否為 s+s 的子字符串即可。

2.3.1 內(nèi)置函數(shù)🥥

class Solution {public boolean rotateString(String s, String goal) {return s.length() == goal.length() && (s+s).contains(goal);}
}

2.3.2 KMP🍊

class Solution {public boolean rotateString(String s, String goal) {// 檢查字符串的長度，如果不相等則返回 falseif (s.length() != goal.length()) return false;// 將字符串 s 進行拼接，以便于處理旋轉(zhuǎn)情況s = s + s;// 生成目標字符串 goal 的前綴函數(shù)數(shù)組int[] next = getNext(goal); int j = 0; // 匹配指針，用于遍歷目標字符串 goal// 遍歷拼接后的字符串 sfor (int i = 0; i < s.length(); i++) {// 當前字符不匹配時，根據(jù)前綴函數(shù)回退 jwhile (j > 0 && s.charAt(i) != goal.charAt(j)) j = next[j - 1];if (s.charAt(i) == goal.charAt(j)) j++;// 如果字符匹配，增加 j// 如果 j 達到目標字符串的長度，表示完全匹配，返回 trueif (j == goal.length()) return true;}// 如果沒有找到匹配，返回 falsereturn false;}// 生成目標字符串的前綴函數(shù)數(shù)組public int[] getNext(String s) {int n = s.length();int[] next = new int[n]; // 存儲前綴函數(shù)的數(shù)組int j = 0; // 前綴指針next[0] = 0; // 第一個字符的前綴長度為0// 遍歷字符串，生成前綴函數(shù)數(shù)組for (int i = 1; i < n; i++) {// 當前字符不匹配時，回退前綴指針 jwhile (j > 0 && s.charAt(i) != s.charAt(j)) j = next[j - 1];if (s.charAt(i) == s.charAt(j)) j++;// 如果字符匹配，前綴長度增加next[i] = j;// 記錄前綴長度到 next 數(shù)組}return next; // 返回前綴函數(shù)數(shù)組}
}

---

都看到這了，不妨一鍵三連再走吧！

🌈歡迎和毛毛張一起探討和交流！
聯(lián)系方式參見個人主頁： 神馬都會億點點的毛毛張

---