A slightly more concise implementation


  • 0
    K

    Re: C# - O(n/k) solution

    Forgot to say that O(n/k) is only an approximation but the fit is pretty good (use a spreadsheet to verify if you like). BTW: an even more concise solution but less readable:

            // Best implementation, minimal code
            // Space: O(1)
            // Complexity: O(n/k) 
            public string ReverseStr_Best(string s, int k)
            {
                // Catch error conditions
                if (string.IsNullOrEmpty(s) || k < 2) return s;
    
                char[] a = s.ToCharArray();
                for (int n = 0; n < s.Length; n += 2 * k)
                {
                    // Determine where the current reverse should end: either (a) after transversing k characters or (b) coming to the end of the string (whichever is smaller)
                    int m = Math.Min(n + k, s.Length);
    
                    // Inner-loop performs the actual reversing of the characters
                    for (int j = n; j < m; j++) a[m - (j - n) - 1] = s[j];
                }
    
                return new string(a);
            }
    

    Software is all about trade-offs. If I were implementing this for real, I'd go for the ReverseStr_Better implementation because it is more maintainable in the long-term.


  • 0
    K

    Even more concise implementation but infinitely less maintainable.

            // Best implementation, minimal code
            // Space: O(n)
            // Complexity: O(n/k) 
            public string ReverseStr_Minimal(string s, int k)
            {
                if (string.IsNullOrEmpty(s) || k < 2) return s;
    
                char[] a = s.ToCharArray();
                for (int n = 0; n < s.Length; n += 2 * k)
                    for (int j = n, m = Math.Min(n + k, s.Length); j < m; j++) a[m - (j - n) - 1] = s[j];
    
                return new string(a);
            }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.