C++ Text Justification Solution


  • 0
    L
    class Solution {
    public:
        vector<string> fullJustify(vector<string> const& words, int maxWidth) {
            std::vector<std::string> result;
            result.reserve(words.size());
    
            auto currentWord    = std::begin(words);
            auto wordsEnd       = std::end(words);
    
            while(currentWord != wordsEnd)
            {
                // Add a new line to the result.
                // we will place the words directly into this string so create it the correct size.
                result.emplace_back(maxWidth, ' ');
    
                auto lineEnd     = currentWord;
                auto currentSize = -1;
                auto wordCount   = 0;
    
                // Find the set of words we want place on this line.
                while(lineEnd != wordsEnd && currentSize + lineEnd->size() + 1 <= maxWidth)
                {
                    currentSize += lineEnd->size() + 1;
                    ++wordCount;
                    ++lineEnd;
                }
    
                // Calculate the extra spacing required.
                auto ExtraSpacePerWord = 0;
                auto unevenSpace       = 0;
    
                // Special case the last line. No extra spaces.
                if (lineEnd != wordsEnd)
                {
                    // Special case two word line. All the spaces go between the two words.
                    if (wordCount <= 2)
                    {
                        ExtraSpacePerWord  = maxWidth - currentSize;
                    }
                    else
                    {
                        // Otherwise calculate the spaces we need to add.
                        auto ExtraSpaces  = maxWidth - currentSize;
                        ExtraSpacePerWord = ExtraSpaces / wordCount;
                        unevenSpace       = ExtraSpaces - (ExtraSpacePerWord * (wordCount - 1));
                    }
                }
    
                // Add the first word.
                auto put = std::copy(std::begin(*currentWord), std::end(*currentWord), std::begin(result.back()));
    
                // Loop over the second and subsequent words.
                // prefix each word with the required spaces.
                for(++currentWord; currentWord != lineEnd; ++currentWord)
                {
                    put += (1
                            + ExtraSpacePerWord
                            + (unevenSpace >= wordCount ? (--unevenSpace, 1) : 0)
                            + (unevenSpace ? (--unevenSpace,1) : 0));
                    put = std::copy(std::begin(*currentWord), std::end(*currentWord), put);
                }
            }
            return result;
        }
    };
    

Log in to reply
 

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