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(""));
row.clear();
rowLetters = 0;
}
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(" ");

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)]
``````