C# - String reversal

字串反轉算是基礎的考題，不論在學校或是工作，拿來作為考題或面試題都會是必經的一道題。

首先，你會拿到一個題目，題目內容是將看到的字串反轉，通常會拿到一個固定的字串去反轉，但在這裡，我建立一個方法亂數產生字串，並且有一個必須傳入的參數——length，每次 Random 時都可以自由配置字串的長度。

/// <summary>
/// 取得亂數產生的字串
/// </summary>
/// <param name="length"></param>
/// <returns></returns>
public static string RandomString(int length)
{
    string str = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789";
    Random random = new Random(Guid.NewGuid().GetHashCode());
    StringBuilder sb = new StringBuilder();

    for (int i = 0; i < length; i++)
        sb.Append(str[random.Next(0, str.Length)]);

    return sb.ToString();
}

題目準備好後，下一步就來解題，目前我只有想到四種反轉方法，如果你有其他的方法，不論好與壞，請不要吝嗇留言告訴我～

暴力破解法
比較直覺的做法，從尾到頭遍歷所有字符，並將每次遍歷的字符加到新的變數裡

/// <summary>
/// 暴力破解 O(n)
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static string ReverseCase1(string s)
{
    string res = string.Empty;

    for (int i = s.Length - 1; i >= 0; i--)
        res += s[i];

    return res;
}

LINQ
直接使用 LINQ 的 Reverse 方法，寫起來簡易明瞭又快速

/// <summary>
/// LINQ Reverse method
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static string ReverseCase2(string s)
{
    return string.Join("", s.Reverse());
}

頭尾位置對調
運用厲害一點的演算法來解——頭尾文字的位置對調，暴力破解迭代了所有字符，而這個方法只需要迭代一半的字符，等於時間複雜度減少了一半，整體效能優於暴力破解。

/// <summary>
/// 頭尾對調位置 O(n/2)
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static string ReverseCase3(string s)
{
    char[] c = s.ToCharArray();

    int i = 0;
    int j = s.Length - 1;

    // you can also use a for loop to iterate
    while (i < j)
    {
        // swap
        char temp = c[i];
        c[i] = c[j];
        c[j] = temp;

        i++;
        j--;
    }

    return new string(c);
}

C# Array 原生反轉方法
最後，一定要知道的 Array.Reverse() C# 原生方法，反轉前先將字串轉換成 Array，反轉完後再 new 成一個新的字串

/// <summary>
/// C# Array 原生反轉方法
/// </summary>
/// <param name="s"></param>
/// <returns></returns>
public static string ReverseCase4(string s)
{
    char[] c = s.ToCharArray();

    Array.Reverse(c);

    return new string(c);
}

寫一個測試 Action 執行時間的方法

/// <summary>
/// 測試 Action 執行時間
/// </summary>
/// <param name="action"></param>
/// <param name="methodName"></param>
static void TestTime(Action action, string methodName)
{
    Stopwatch sw = new Stopwatch();

    sw.Start();
    action();
    sw.Stop();

    Console.WriteLine($"Duration: {sw.ElapsedMilliseconds:N0}ms, TestName:{methodName}");
}

Main 方法

static void Main(string[] args)
{
    // six nines
    var str = GetRandomString(100000);

    TestTime(() => ReverseCase1(str), "暴力破解");
    TestTime(() => ReverseCase2(str), "LINQ 反轉方法");
    TestTime(() => ReverseCase3(str), "頭尾對調位置");
    TestTime(() => ReverseCase4(str), "C# Array 原生反轉方法");
}

執行結果
因為暴力破解遍歷的所有字符，沒有意外的話它會是執行時間最久的方法

第一次執行結果，可以看到暴力破解法的時間複雜度相對高，僅次於後的是 LINQ 方法，而後兩種方法無法比較。

如果加大長度同時去跑這四種方法，會因為暴力破解法的執行時間過長而等待，為了再更清楚的看到後兩種方法執行狀況，將前兩種方法註解，只運行後兩種方法，並且加大參數長度為 9999999

比較就明顯出來了，雖然頭尾對調是優化過的演算法，甚至比 LINQ 的執行效率更高，但還是輸給 C# Array 的原生方法。

或許 Array 底層的最佳化是基於頭尾對調的邏輯去執行的…？

---

Thanks for reading the article 🌷 🌻 🌼

If you like it, please don't hesitate to click heart button ❤️
or follow my GitHub ⭐ I'd appreciate it.

---