Given an array of words and a maxWidth of length, reformat the words so that each line is exactly maxWidth and aligned to the left and right sides of the text.

You should use a “greedy algorithm” to place a given word; That is, put as many words in each line as possible. Padding with Spaces “if necessary, so that each line has exactly maxWidth characters.

The number of Spaces between words should be distributed as evenly as possible. If the space between words on a line is not evenly distributed, more space is placed on the left than on the right.

The last line of text should be left aligned and no extra Spaces inserted between words.

Description:

  • A word is a sequence of characters that is not a space character.
  • Each word has a length greater than 0, less than or equal tomaxWidth.
  • Input word arraywordsContains at least one word.

Example:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."] maxWidth = 16 [ "This is an", "example of text", "justification. " ]Copy the code

Their thinking

1. Use the array vint to store the length of each string.

2. Define a string s and fill it with as many words as possible.

  • Define an integersumTo determinesum+vint[addr]If more thanmaxWidthIf the value is greater than or equal to, whether to add space is required; if the value is smaller than or equal to, whether to add space is requiredsum=sum+vint[addr]+1;s=s+words[addr]+" "; +1 is because there must be a space between each word, and the end of the loop pops up a space at the end;

3, fill space operation:

  • Set the number of Spaces to be filled equal tospace,space=space=maxWidth-sum+1; + 1The number of inserted words size was recorded in the operation of string S in the previous step, because the remaining lines can only insert Spaces between words except the left align of the last line. In this case, size should be reduced by one, namely size–, because there are only size– places to place Spaces.
  • And then determine if it’s the last rowaddr>=words.size()Now the number of words in the last line is greater than1, i.e.,size>0; namelyaddr>=words.size()&&size>0; Size ==0; size==0; Insert a space at the end, or a space at s_addr[I] if it is larger than one word (the position of the fill space was recorded in the previous string operation s_ADDR array)s_addrInsert, updates_addrSave the subscripts_addr[i]=s_addr[i]+k;kRepresents each timeiThe subscript after the space is moved back1Bit, and then proceedi=i%size; That is cyclic insertion wheni==0When,kReset;

4, ANS tail into s;

code

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<int> vint;
        vector<string> ans;
        for(auto &x:words){// Store the length of each string
            vint.push_back(x.size());
        }

        int addr=0;
        while(addr<words.size()) {int sum=0;
            string s;
            int size=0;
            vector<int> s_addr;
            while(sum+vint[addr]<=maxWidth){// Place strings wherever possible
                sum+=vint[addr]+1;
                s=s+words[addr]+"";
                s_addr.push_back(sum- 1);
                addr++;// Record the location
                size++;// Count the number of words
                if(addr>=words.size()) break;
            }
            s.pop_back(a);// Pop up trailing space
            int space=maxWidth-sum+1;// Record the number of Spaces that need to be filled
            size--;// There are several places to insert Spaces
            if(addr>=words.size()&&size>0)// Determine if it is the last line
            {/ / is at the end of the line
                while(space>0){
                    s.push_back(' '); space--; }}else{// Not the last line
                if(space>0) {int i=0;
                int k=0;
                while(space>0) {if(size! =0) {While (space>0) (space>0)
                        s.insert(s_addr[i]+k,1.' ');
                        s_addr[i]=s_addr[i]+k;// Update the subscript
                        i++;
                        i=i%size;// loop subscript
                        k++;
                        if(i==0)k=0;/ / k reset
                        space--;
                    }else{// Is a word
                        s.push_back(' ');// Add it directly at the end
                        space--;
                    }
                }
                }
            }
            
            ans.push_back(s);
        }
        returnans; }};Copy the code