Skip to content

68. Text Justification 👎

  • Time: $O(\Sigma |\texttt{words[i]}|)$
  • Space: $O(1)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
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>& words, const string& s) {
    string joined;
    for (int i = 0; i < words.size(); ++i) {
      joined += words[i];
      if (i != words.size() - 1)
        joined += s;
    }
    return joined;
  }

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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)]