My 3ms c++ solution


  • 0
    P
    class Solution {
    public:
        vector<string> fullJustify(vector<string> &words, int L) {
            vector<string> result;
            int size = words.size();
            if (size == 0) {
                return result;
            }
            
            int i = 1;
            int start = 0;
            int cur_word_len = words[0].length();
            int cur_total_len = cur_word_len;
            while(i < size) {
                cur_word_len = words[i].length();
                if (cur_total_len + 1 + cur_word_len <= L) {
                    //take in the current word
                    cur_total_len += cur_word_len + 1;
                } else {
                    int extra_spaces = L - cur_total_len;
                    string s = getStrTillL(words, start, i-1, extra_spaces);
                    if (s.length() != L) {
                        addSpaces(s, L-s.length());
                    }
                    result.push_back(s);
                    start = i;
                    cur_total_len = cur_word_len;
                }
                i++;
            }
            
            string s = getStrTillL(words, start, size-1, 0);
            int spaces = L-s.length();
            addSpaces(s, spaces);
            //s += '\0';
            result.push_back(s);
            return result;
        }
        
        void addSpaces(string& s, int num_spaces) {
            for (int i = 0; i < num_spaces; ++i) {
                s += " ";
            }
            //s += '\0';
        }
        
        string getStrTillL(vector<string>& words, int start, int end, int extra_spaces) {
            string result = "";
            if (start == end) {
                result.append(words[start]);
                addSpaces(result, extra_spaces);
                return result;
            }
            int num_pad_spaces = end-start;
            int left_over = extra_spaces%num_pad_spaces;
            int standard_spaces = (extra_spaces-left_over)/num_pad_spaces;
            for (int i = start; i < end; ++i) {
                result += words[i];
                int num_spaces = 0;
                if (left_over > 0) {
                    num_spaces = standard_spaces + 2;
                    left_over--;
                } else {
                    num_spaces = standard_spaces + 1;
                }
                addSpaces(result, num_spaces);
            }
            result += words[end];
            return result;
        }
    };

Log in to reply
 

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