C# Two understandable solutions - O(n) and O(1) space.


  • -1
    L

    The basic idea of both solutions is to reverse the string in its entirety, then reverse each individual word and remove spaces.

    O(n)

    String.split(null); will split on all whitespace characters. We then filter out all blank strings, reverse the remainder, and join them together with a single string.

    public class Solution
        {
            public string ReverseWords(string s) => String.Join(" ", s.Split(null).Where(k => !String.IsNullOrWhiteSpace(k)).Reverse());
        }
    

    O(1)

    This can be done efficiently in-place via keeping track of the number of blank spaces which have previously been processed, along with a count of the number of letters in the currently processed string.

    As the correct string is built from left to right, there will be a suffix of empty spaces after the processed string. Knowing the length of the suffix allows us to:

    • Skip to the end of the suffix in the search for the next character
    • Stop reversing once we have reached the end of the next string (as we know all intermediate characters will be blank spaces).
     public class Solution
     {
        public string ReverseWords(string s)
        {
            IList<char> c = s.ToCharArray();
            reverse(c, 0, c.Count - 1, c.Count);
            int start = 0, blankCount = 0;
            while(start + blankCount < c.Count)
            {
                int nextSpace = start; 
                while (blankCount + nextSpace < c.Count && c[nextSpace + blankCount] == ' ') blankCount++;
                while (blankCount + nextSpace < c.Count && c[nextSpace + blankCount] != ' ') nextSpace++;
                reverse(c, start, blankCount + nextSpace - 1, nextSpace - start);
                start = nextSpace + 1;
            }
            return string.Join("", c).Trim();
        }
    
        private void reverse(IList<char> c, int start, int end, int length)
        {
            while(start < end && --length >= 0)
            {
                var t = c[start];
                c[start] = c[end];
                c[end] = t;
                start++;
                end--;
            }
        }
    }

Log in to reply
 

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