DEV Community

Cover image for String reversal for C#
FakeStandard
FakeStandard

Posted on • Updated on

String reversal for C#

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

首先,你會拿到一個題目,題目內容是將看到的字串反轉,通常會拿到一個固定的字串去反轉,但在這裡,我建立一個方法亂數產生字串,並且有一個必須傳入的參數——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();
}
Enter fullscreen mode Exit fullscreen mode

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

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

/// <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;
}
Enter fullscreen mode Exit fullscreen mode

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());
}
Enter fullscreen mode Exit fullscreen mode

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

/// <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);
}
Enter fullscreen mode Exit fullscreen mode

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);
}
Enter fullscreen mode Exit fullscreen mode

寫一個測試 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}");
}
Enter fullscreen mode Exit fullscreen mode

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 原生反轉方法");
}
Enter fullscreen mode Exit fullscreen mode

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

pic-004

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

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

pic-005

比較就明顯出來了,雖然頭尾對調是優化過的演算法,甚至比 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
or buy me a coffee ⬇️ I'd appreciate it.

Buy-me-a-coffee

Top comments (0)