C# O(N) Accepted solution with comments


  • 1
    J
    public IList<string> FullJustify(string[] words, int maxWidth) 
        {
            // This solution is O(n) because even though we have a nested while loop, each element in the array is only visited twice
            // This is not including the loops to fill out string with spaces. (I've assumed that these loops are of constant time complexity because the max numebr of spaces added to a string is maxWidth)
            
            var result = new List<string>();
            if (words.Length == 0) return result;
            if (maxWidth == 0) return words.ToList();
            
            if (words.Length == 1)
            {
                var str2 = words[0];
                for (int i = 0; i < maxWidth-words[0].Length; i++)
                {
                    str2+=" ";
                }
                result.Add(str2);
                return result;
            }
            
            var index = 0; var secondindex = 0;
            var lengthwithspaces = 0; // keeps track of the length of word + minimum white space required
            var actuallength = 0; // keeps track of the actual length of words, without including white space.
            var numspacesrequired = 0; // keeps track of num of white spaces required for a string. Can be calculated from 
            // index and secondindex values as well, but this way seemed better to me.
            var list = new List<string>();
            while (index < words.Length)
            {
                var prev = lengthwithspaces; // Everytime we check lengthwithspaces, we're adding the extra 1 length for space.
                // suppose we add a word and that fits maxWidth perfectly, the +1 will give us the incorrect value, so the if 
                // block contains both checks. Hence I've used prev.
                lengthwithspaces += words[index].Length+1;
               
                if (lengthwithspaces >= maxWidth && prev+words[index].Length > maxWidth)
                {
                   // We need to reduce the numspacesrequired because we incremented on par with number of words added, but
                   // we only need (num of words - 1). If there are three words, we only need two spaces. 
                    numspacesrequired--;
                    var reminder = 0;
                    var totalspaceslength = (maxWidth - actuallength);
                    
                    // The idea of doing two whitespace variables is to evenly spread out the white spaces between the words. 
                    // We just need two, since the white spaces will only be of length divisor or divisor+1. The idea is to
                    // divide the total length of white spaces with num of white spaces, so that we figure out how many white 
                    // spaces the variable needs to have.
                    
                    var divisor = (numspacesrequired == 0) ? 0 : totalspaceslength/numspacesrequired;
                    reminder = (numspacesrequired == 0) ? 0 : totalspaceslength%numspacesrequired;
                    var whitespace1 = ""; var whitespace2 = "";
                    
                    for (int i = 0; i < divisor; i++)
                    {
                        whitespace1 += " ";
                        whitespace2 += " ";
                    }
                    if (reminder != 0) whitespace1 += " "; // All white spaces won't be of equal length
                    var str = "";
                   
                    while (secondindex < index)
                    {
                        str += words[secondindex];
                        // for all the words that need to be added into the last sentence, append them with the
                        // appropriate space values.
                        if (secondindex != index-1)
                        {
                            if (numspacesrequired > 0 && reminder > 0)
                            {str += whitespace1;} 
                            else if (numspacesrequired > 0 && divisor != 0)
                            {str += whitespace2; }
                        }
                        else
                        {
                            // Fill out the string with spaces to make it as long as maxWidth
                            if (str.Length < maxWidth)
                            {
                                var len = str.Length ;
                                while (len < maxWidth)
                                {
                                    str += " "; len++;
                                }
                            }
                        }
                        reminder--;
                        numspacesrequired--;
                        secondindex++;
                    }
                    // reset the values.
                    lengthwithspaces = 0;
                    actuallength = 0;
                    numspacesrequired = 0;
                    result.Add(str);
                }
                else
                {
                    // increment the values.
                    actuallength += words[index].Length;
                    index++;
                    numspacesrequired++;
                }
            }
            
            // Add the last string to the list.
            // Because this is the last line, we will simply add a normal " ", and fill out the end with spaces.
            // As per the last line in the question.
            var reminder1 = 0;
            var totalspaceslength1 = (maxWidth - actuallength);
            var divisor1 = (numspacesrequired == 0) ? 0 : totalspaceslength1/numspacesrequired;
            reminder1 = (numspacesrequired == 0) ? 0 : totalspaceslength1 % numspacesrequired;
            var whitespace11 = " ";
            
            var str1 = "";
            // for all the words that need to be added into the last sentence, append them with a single space.
            while (secondindex < index)
            {
                str1 += words[secondindex];
                if (secondindex != index-1)
                {
                    if (numspacesrequired > 0) str1 += whitespace11;
                }
                numspacesrequired--;
                secondindex++;
            }
            lengthwithspaces = 0;
            actuallength = 0;
            numspacesrequired = 0;
            
            if (str1.Length < maxWidth)
            {
               // Fill out the string with spaces to make it as long as maxWidth
                var len1 = str1.Length ;
                while (len1 < maxWidth)
                {
                    str1 += " "; len1++;
                }
            }
            result.Add(str1);
            return result;
        }
    

Log in to reply
 

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