Leetcode

Text Justification

  • Time:O(\Sigma |\texttt{words[i]}|)
  • Space:O(1)

C++

class Solution {
 public:
  vector<string> fullJustify(vector<string>& words, size_t maxWidth) {
    vector<string> ans;
    vector<string> row;
    size_t rowLetters = 0;

    for (const string& word : words) {
      // if we put the word in this row, it'll exceed the maxWidth,
      // so we cannot put the word to this row and have to pad spaces to
      // each word in this row
      if (rowLetters + row.size() + word.length() > maxWidth) {
        const int spaces = maxWidth - rowLetters;
        if (row.size() == 1) {
          // pad all spaces after row[0]
          for (int i = 0; i < spaces; ++i)
            row[0] += " ";
        } else {
          // evenly pad spaces to each word (expect the last one) in this row
          for (int i = 0; i < spaces; ++i)
            row[i % (row.size() - 1)] += " ";
        }
        ans.push_back(join(row, ""));
        row.clear();
        rowLetters = 0;
      }
      row.push_back(word);
      rowLetters += word.length();
    }
    ans.push_back(ljust(join(row, " "), maxWidth));

    return ans;
  }

 private:
  string join(const vector<string>& v, const string& c) {
    string s;
    for (auto p = begin(v); p != end(v); ++p) {
      s += *p;
      if (p != end(v) - 1)
        s += c;
    }
    return s;
  }

  string ljust(string s, int width) {
    for (int i = 0; i < s.length() - width; ++i)
      s += " ";
    return s;
  }
};

JAVA

class Solution {
  public List<String> fullJustify(String[] words, int maxWidth) {
    List<String> ans = new ArrayList<>();
    List<StringBuilder> row = new ArrayList<>();
    int rowLetters = 0;

    for (final String word : words) {
      if (rowLetters + row.size() + word.length() > maxWidth) {
        final int spaces = maxWidth - rowLetters;
        if (row.size() == 1) {
          for (int i = 0; i < spaces; ++i)
            row.get(0).append(" ");
        } else {
          for (int i = 0; i < spaces; ++i)
            row.get(i % (row.size() - 1)).append(" ");
        }
        final String joinedRow =
            row.stream().map(StringBuilder::toString).collect(Collectors.joining(""));
        ans.add(joinedRow);
        row.clear();
        rowLetters = 0;
      }
      row.add(new StringBuilder(word));
      rowLetters += word.length();
    }

    final String lastRow =
        row.stream().map(StringBuilder::toString).collect(Collectors.joining(" "));
    StringBuilder sb = new StringBuilder(lastRow);
    final int spacesToBeAdded = maxWidth - sb.length();
    for (int i = 0; i < spacesToBeAdded; ++i)
      sb.append(" ");

    ans.add(sb.toString());
    return ans;
  }
}

Python

class Solution:
  def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
    ans = []
    row = []
    rowLetters = 0

    for word in words:
      if rowLetters + len(word) + len(row) > maxWidth:
        for i in range(maxWidth - rowLetters):
          row[i % (len(row) - 1 or 1)] += ' '
        ans.append(''.join(row))
        row = []
        rowLetters = 0
      row.append(word)
      rowLetters += len(word)

    return ans + [' '.join(row).ljust(maxWidth)]