Text Justification by C++


  • 0
    P

    The solution is straight-forward, every time we find a string int the words, we check if we can add it to the current line, when we can not add more string into current line, we format current line. The details is listed below:

    1.check if string can be added to current line:
    we use an variable cur_size to store the length of current line so far. so if cur_size + string.size > maxWidth, we can not add string to current line, we need to format current line.

    2.format current line strs:
    we use ls to indicate how many spaces we need to add to current line between words, use N to indicate how many places we need to add spaces, then we get two vaiables:
    K = ls / N K is the average spaces we need to add to these places(between words);
    M = ls % N M is the spaces we can not divided evenly, we add one each to the places on the left.

    //format current line
    string pack(vector<string> & strs, int L, bool isLast){
      string ret = "";
      int len = 0;
      for(int i = 0; i < strs.size(); i ++) len += strs[i].size();
      int ls = L - len;// the spaces we need to add to current line
      if(strs.size() == 1){
        //if there is only one word in current line, pack it to left
        ret = strs[0];
        ret.append(string(ls, ' '));
        return ret;
      }else if(isLast){
        // if current line is the last line, pack all the words to left
        for(int i = 0; i < strs.size(); i ++){
          ret.append(strs[i]);
          ret.append(" ");
          ls --;
        }
        //!!! erase spaces when ls < 0
        if(ls < 0){
          while(ls < 0) {ret.pop_back();ls ++;}
        }else{
          while(ls > 0) {ret.append(" "); ls --;}
        }
        return ret;
      }else{
       // distibute the spaces evenly
        int N = strs.size() - 1;
        int K = ls / N;
        int M = ls % N;
        for(int i = 0; i < strs.size() - 1; i++){
          ret.append(strs[i]);
          ret.append(string(K, ' '));
          if(M > 0) {
            ret.append(" ");
            M --;
          }
        }
        ret.append(strs[strs.size() - 1]);
        return ret;
      }
    }
    
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
      vector<string> ret; 
      vector<string> tmp;
      int cur_size = 0;
      for(int i = 0; i < words.size();){
    //check if words[i] can add to current line
        if(cur_size + words[i].size() > maxWidth){
          cur_size = 0;
          ret.push_back(pack(tmp, maxWidth, false));
          tmp.clear();
        }else{
          cur_size += (words[i].size() + 1);
          tmp.push_back(words[i]);
          i ++;
        }
      }
    //handle the last line
      ret.push_back(pack(tmp, maxWidth, true));
      return ret;
    }
    
    

    complicity analyze
    N-- the length of words
    maxWidth -- line width
    L -- maximum length of all the words
    The solution copy all the words to the result lines, we only visit all the word twice, it cost O(2 * N * L), when we construct the result lines, it cost O(N * maxWidth), so the overall time cost is O(2 * N * L + N * maxWidth)

    we use tmp to store words in current lines, it cost O(maxWidth), and we use ret to store the result, it cost O(N * maxWidth), so the overall memory cost isO(N * maxWidth)


Log in to reply
 

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