796. Rotate String

題目 / Problem

中文: 給定兩個字串 s 和 goal,如果 s 經過若干次「移位」操作後可以變成 goal,則回傳 true,否則回傳 false。

一次「移位」操作:把 s 最左邊的字元搬到最右邊。 例如 s = "abcde",經過一次移位後變成 "bcdea"。

English: Given two strings s and goal, return true if and only if s can become goal after some number of shifts. A shift moves the leftmost character of s to the rightmost position. For example, "abcde" becomes "bcdea" after one shift.

Constraints / 限制: - 1 <= s.length, goal.length <= 100 - s 和 goal 只包含小寫英文字母 / both consist of lowercase English letters.

Example / 範例: - Input: s = "abcde", goal = "cdeab" → Output: true (shift 兩次:abcde → bcdea → cdeab) - Input: s = "abcde", goal = "abced" → Output: false

名詞解釋 / Glossary

• Rotation / 旋轉(循環移位): 把字串前面的一段搬到後面。"abcde" 的所有旋轉結果是 "abcde"、"bcdea"、"cdeab"、"deabc"、"eabcd",共 n 種。
• Concatenation / 字串串接: 把兩個字串接在一起。例如 "abcde" + "abcde" = "abcdeabcde"。在 C 裡需要手動配置記憶體並用 strcpy/strcat;在 C++ 直接用 + 即可。
• Substring search / 子字串搜尋: 在一個大字串裡找另一個小字串是否出現過。C 用 strstr,C++ 用 string::find。
• Key insight / 關鍵觀察: s 的所有旋轉結果都是 s + s 的子字串。例如 s = "abcde",則 s+s = "abcdeabcde",而 "cdeab" 確實出現在裡面。這把「枚舉旋轉」變成「一次子字串搜尋」。
• strstr (C): strstr(haystack, needle) 在 haystack 中搜尋 needle,找到則回傳指向匹配位置的指標,找不到則回傳 NULL。
• std::string::find (C++): 成員函式,回傳第一次出現的索引;找不到則回傳特殊常數 string::npos。

思路

最直覺的暴力法是模擬:對 s 進行 n 次旋轉,每次比較是否等於 goal。但這需要實際搬動字元,寫起來繁瑣。更聰明的觀察是:s 的所有旋轉結果,都會以子字串的形式藏在 s + s 裡。原因很簡單,假設旋轉了 k 次,結果就是 s[k..n-1] + s[0..k-1],而這正好對應 s + s 從第 k 位開始長度為 n 的那一段。所以演算法只剩兩件事:先檢查兩字串長度是否相等(不等就直接 false,因為旋轉不改變長度),再檢查 goal 是否為 s + s 的子字串。一個關鍵不變量(invariant)是「旋轉保留長度與字元多重集」,長度檢查保證我們不會誤判類似 "ab" 與 "aab" 的情況。

The brute-force approach simulates: rotate s up to n times and compare with goal each time. That works but is fiddly. A cleaner observation: every rotation of s is a contiguous substring of s + s. If we rotate k times we get s[k..n-1] + s[0..k-1], which is exactly the length-n window in s + s starting at index k. So the algorithm reduces to two checks: lengths must match (rotation preserves length, so unequal lengths immediately give false), and goal must appear as a substring of s + s. The length guard is what stops false positives like s = "ab", goal = "aab" — without it, "aab" would be found inside "abab" even though the strings have different sizes.

逐步走查 / Walkthrough

Example: s = "abcde", goal = "cdeab".

對照失敗例 / Contrast with the failing case: s = "abcde", goal = "abced". s+s = "abcdeabcde",在裡面找 "abced" 找不到 → 回傳 false。

Solution — C

// Algorithm / 演算法:
// 1. 若長度不同直接回傳 false / different lengths → false.
// 2. 把 s 串接自己得到 s+s / concatenate s with itself.
// 3. 用 strstr 在 s+s 裡找 goal,找到即為某種旋轉 / strstr finds goal as a substring iff goal is a rotation of s.

#include <stdbool.h>   // 提供 bool / true / false 型別 / provides the bool type
#include <string.h>    // 提供 strlen / strcpy / strcat / strstr / for string utilities
#include <stdlib.h>    // 提供 malloc / free / for dynamic memory

bool rotateString(char* s, char* goal) {
    size_t n = strlen(s);              // n = s 的長度 / length of s
    size_t m = strlen(goal);           // m = goal 的長度 / length of goal

    if (n != m) return false;          // 長度不同必不可能 / different lengths cannot be rotations

    // 配置 2n+1 個 char 的空間:2n 用來放 s+s,+1 留給結尾的 '' 終止符
    // Allocate 2n+1 bytes: 2n for s+s, plus 1 for the trailing null terminator ''.
    char* doubled = (char*)malloc(2 * n + 1);
    if (doubled == NULL) return false; // 防禦性檢查:malloc 失敗就放棄 / defensive: bail out if malloc fails

    strcpy(doubled, s);                // 先把 s 複製到 doubled / copy s into the buffer
    strcat(doubled, s);                // 再把 s 接在後面,得到 s+s / append s again, yielding s+s

    // strstr 回傳指向匹配位置的指標,沒找到回傳 NULL
    // strstr returns a pointer to the match, or NULL if not found.
    bool found = (strstr(doubled, goal) != NULL);

    free(doubled);                     // 釋放剛剛 malloc 的記憶體,避免洩漏 / free the heap allocation to avoid a leak
    return found;                      // 回傳搜尋結果 / return whether goal appears in s+s
}

Solution — C++

// Algorithm / 演算法:同 C 版本 / same as the C version.
// 1. 長度不等 → false / unequal lengths → false.
// 2. 構造 s+s,檢查 goal 是否為其子字串 / build s+s, test if goal is a substring.

#include <string>   // std::string 與其成員函式 / for std::string and its methods

class Solution {
public:
    // 用 const string& 接收參數,避免複製整個字串 / pass by const reference to avoid copying.
    bool rotateString(const std::string& s, const std::string& goal) {
        if (s.size() != goal.size()) return false;   // 長度檢查必不可少 / length must match first

        // s + s 直接用運算子重載完成串接,結果是新的 std::string
        // operator+ on std::string concatenates and returns a new string.
        std::string doubled = s + s;

        // find 回傳第一次出現的索引,沒找到回傳特殊常數 string::npos
        // find returns the index of the first occurrence, or string::npos if not found.
        return doubled.find(goal) != std::string::npos;
    }
};

複雜度 / Complexity

• Time: O(n²) — n 是 s 的長度。串接 s+s 是 O(n);標準庫的子字串搜尋(strstr / string::find)在最壞情況下是 O(n·m) = O(n²),因為 s+s 長度是 2n,goal 長度是 n。在題目限制 n ≤ 100 下完全足夠。
• Space: O(n) — 需要額外 2n+1 個字元的緩衝區存放 s+s / we allocate roughly 2n extra chars to hold the doubled string.

Pitfalls & Edge Cases

• 長度不等 / Unequal lengths: 若漏掉長度檢查,當 s = "a"、goal = "aa" 時,s+s = "aa" 會包含 "aa",錯誤回傳 true。先比較長度可徹底避免。 / Without the length guard, a shorter s whose doubled form happens to contain goal would wrongly return true.
• C 的 '\0' 終止符 / Null terminator in C: malloc(2*n) 不夠,必須是 2*n + 1,否則 strcpy/strcat 寫出邊界,造成未定義行為。 / Forgetting the +1 byte for '\0' causes a buffer overflow.
• 記憶體釋放 / Freeing memory: 在 C 版本中 malloc 後一定要 free,否則每次呼叫都會洩漏。LeetCode 的 judge 會多次呼叫你的函式。 / Always free heap allocations to avoid leaks across repeated test cases.
• 空字串 / Empty strings: 題目保證長度 ≥ 1,不會遇到。但若真的兩者皆空,s+s = "",find("") 回傳 0,結果為 true,符合直覺(空字串是空字串的旋轉)。 / The constraints rule this out, but the algorithm still behaves correctly.
• 混淆「子字串」與「子序列」 / Substring vs subsequence: 子字串必須是連續的;strstr 與 string::find 找的正是連續匹配,符合旋轉的定義。 / Rotations are contiguous slices of s+s, which is exactly what substring search checks.