【完虐演算法】字元串-旋轉詞 復盤總結
大家好吖，我是Johngo！
有幾天沒有更新文章了，居然把前幾天的送書的事情忘記了。
今天一起吧！！
說在前面
言歸正傳，這一期來說說字元串的第三塊內容「字元串 – 旋轉詞」
github：//github.com/xiaozhutec/share_leetcode
文檔地址：//github.com/xiaozhutec/share_leetcode/tree/master/docs
整體架構：
字元串 – 旋轉詞
今天這期內容是字元串的第三期。
首先，把什麼是旋轉詞進行一個簡單的說明：
所謂字元串的旋轉，分為左右旋轉。
以左旋轉為例：就是把字元串前面的若干字元轉移到字元串的尾部這樣的操作
比如說字元串 “abcdefg” 左旋轉 2 個三位，得到字元串 “abcdefg”。
字元串「旋轉詞」方面的問題（還拿字元串 “abcdefg” 和 “cdefgab” 為例）
令 A = “abcdefg”，B = “cdefgab”
一般的思路是：
將 A = A+A，判斷 字元串 B 是否被包含進去字元串 A+A。
下圖為例，將 A 做 A = A+A 的操作，形成一個大字元串
之後，判斷字元串 B 是否被包含進上圖中的大字元串即可解決。
發現，正好匹配，問題解決！
說明字元串 A 和字元串 B 互為旋轉詞。
案例
整體關於字元串「旋轉詞」方面的問題是比較簡單的，個人認為只要掌握其一般思路即可。
下面會通過兩個案例進行舉例，分別是 LeetCode 的 796 題 和 劍指 Offer 58 題
796.旋轉字元串【簡單】
劍指 Offer 58 – II. 左旋轉字元串【簡單】
796.旋轉字元串【簡單】
給定兩個字元串, A 和 B。
A 的旋轉操作就是將 A 最左邊的字元移動到最右邊。 例如, 若 A = ‘abcde’，在移動一次之後結果就是’bcdea’ 。如果在若干次旋轉操作之後，A 能變成B，那麼返回True。
輸入: A = 'abcde', B = 'cdeab' 輸出: true
整體這個題目還是比較簡單的，解決的思路就是上述介紹的方式。
即 字元串 A+A 包含字元串 B：
實現起來也很簡單，就一行即可。
咱們直接用 Python 來解決：
class Solution(object):
def rotateString(self, s, goal):
return len(s) == len(goal) and s in goal+goal
在這裡利用了 Python 固有的方式，可以進行子串判斷。
事實上，還有一種演算法咱們是需要著重掌握的，那就是著名的 KMP 演算法。
KMP 演算法是專門用來判斷子串判斷的演算法，後面有一期會非常詳細的就 KMP 進行分享。
劍指 Offer 58 – II. 左旋轉字元串【簡單】
字元串的左旋轉操作是把字元串前面的若干個字元轉移到字元串的尾部。請定義一個函數實現字元串左旋轉操作的功能。比如，輸入字元串”abcdefg”和數字2，該函數將返回左旋轉兩位得到的結果”cdefgab”。
輸入: s = "abcdefg", k = 2 輸出: "cdefgab"
這個題目雖然也是標記的簡單，但需要加一步驟，就是給定的 k 值。
也可以分為兩種思路解決。
方法一：s2 = s + s，得到s[k, size(s)+k]即為原字元串 s 旋轉了 k 個位置的旋轉詞
方法二：將字元串的 s 的前 k 位複製一份接到字元串 s 的最後，得到 s[k:] 為 s 旋轉了 k 個位置的旋轉詞
好！先來看看方法一：
拼接字元串 s，然後當 k=2的時候，截取固定長度（字元串 s 的長度）。
最後返回截取的字元串，得到答案。
看超級簡約的程式碼：
class Solution(object):
def reverseLeftWords(self, s, n):
size = len(s)
s2 = s + s
return s2[n:size+n]
或者再簡約點：
class Solution(object):
def reverseLeftWords(self, s, n):
s2 = s + s
return s2[n:len(s)+n]
再看方法二：
將前 k 個元素，依次接到字元串 s 的後邊。
進而獲取固定長度（字元串 s 的長度）的字元串，得到答案。
簡潔的程式碼來了：
class Solution(object):
def reverseLeftWords1(self, s, n):
size = len(s)
for i in range(n):
s += s[i]
return s[n:]
還可以更加簡潔一些， 即不用循環，直接截取前 k 個字元拼接到 s 的最後即可！
好了，今天內容比較簡單一些。就是關於字元串「旋轉詞」進行了分享。
另外，方便的話也在我的github👇 加顆星，它是我持續輸出最大最大的動力，感謝大家！
github：//github.com/xiaozhutec/share_leetcode
如果感覺內容對你有些許的幫助，求點贊，求在看！
下期想看哪方面的，評論區告訴我！
下面不要忘記抽取福利吖，好了~ 咱們下期見！bye~~
