C#LeetCode刷题之#344-反转字符串​​​​​​​（Reverse String）

问题

编写一个函数，其作用是将输入的字符串反转过来。

输入: “hello”

输出: “olleh”

输入: “A man, a plan, a canal: Panama”

输出: “amanaP :lanac a ,nalp a ,nam A”

Write a function that takes a string as input and returns the string reversed.

Input: “hello”

Output: “olleh”

Input: “A man, a plan, a canal: Panama”

Output: “amanaP :lanac a ,nalp a ,nam A”

示例

public class Program {

    public static void Main(string[] args) {
        var s = "A man, a plan, a canal: Panama";

        var res = ReverseString(s);
        Console.WriteLine(res);

        s = "private static string ReverseString(string s)";

        res = ReverseString2(s);
        Console.WriteLine(res);

        s = "using System.Collections.Generic;";

        res = ReverseString3(s);
        Console.WriteLine(res);

        s = "var res = ReverseString(s);";

        res = ReverseString4(s);
        Console.WriteLine(res);

        s = "Console.WriteLine(res);";

        res = ReverseString5(s);
        Console.WriteLine(res);

        s = "var sb = new StringBuilder();";

        res = ReverseString6(s);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static string ReverseString(string s) {
        //LeetCode超时未AC
        var stack = new Stack<char>();
        foreach(var c in s) {
            stack.Push(c);
        }
        var res = string.Empty;
        while(stack.Count != 0) {
            res += stack.Pop();
        }
        return res;
    }

    private static string ReverseString2(string s) {
        //LeetCode超时未AC
        var list = new List<char>();
        foreach(var c in s) {
            list.Add(c);
        }
        var res = string.Empty;
        for(var i = list.Count - 1; i >= 0; i--) {
            res += list[i];
        }
        return res;
    }

    private static string ReverseString3(string s) {
        var length = s.Length;
        var i = 0;
        var j = length - 1;
        var chars = new char[length];
        while(i <= length - 1) {
            chars[j] = s[i];
            i++;
            j--;
        }
        return new string(chars);
    }

    private static string ReverseString4(string s) {
        var chars = s.ToCharArray();
        var start = 0;
        var end = s.Length - 1;
        while(start < end) {
            var swap = chars[start];
            chars[start] = chars[end];
            chars[end] = swap;
            start++;
            end--;
        }
        return new String(chars);
    }

    private static string ReverseString5(string s) {
        var sb = new StringBuilder();
        for(var i = s.Length - 1; i >= 0; i--) {
            sb.Append(s[i]);
        }
        return sb.ToString();
    }

    private static string ReverseString6(string s) {
        var arr = s.ToCharArray();
        Array.Reverse(arr);
        return new string(arr);
    }

}

以上给出6种算法实现，以下是这个案例的输出结果：

amanaP :lanac a ,nalp a ,nam A
)s gnirts(gnirtSesreveR gnirts citats etavirp
;cireneG.snoitcelloC.metsyS gnisu
;)s(gnirtSesreveR = ser rav
;)ser(eniLetirW.elosnoC
;)(redliuBgnirtS wen = bs rav

分析：

显而易见，以上6种算法的时间复杂度均为： 。