68. Text Justification
time: O(w*L), almot w, words nums
space: O(smaller than w)
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> res = new ArrayList<>();
if (words == null || words.length == 0) {
return res;
}
List<String> list = new ArrayList<>(); // single line data
int len = 0;
for (String word : words) {
if (list.isEmpty() || len + list.size() + word.length() <= maxWidth) { // keep adding to this line
list.add(word);
len += word.length();
} else { // over single line limit, add data to res
StringBuilder sb = new StringBuilder();
int spaceCnt = maxWidth - len;
int intervals = list.size() - 1;
if (intervals == 0) { // means single word in a line
sb.append(list.get(0));
for (int i = 0; i < spaceCnt; i++) {
sb.append(" ");
}
} else {
int extraSpace = spaceCnt % intervals; // ex: 10%3 = 1
int eachIntervalSpace = spaceCnt / intervals;
String space = getSpace(eachIntervalSpace, new StringBuilder());
sb.append(list.get(0));
for (int i = 1; i < list.size(); i++) {
sb.append(space);
if (extraSpace != 0) {
sb.append(" ");
extraSpace--;
}
sb.append(list.get(i));
}
}
res.add(sb.toString());
len = word.length();
list = new ArrayList<>();
list.add(word);
}
}
//last line
StringBuilder sb = new StringBuilder();
sb.append(list.get(0));
for (int i = 1; i < list.size();i++) {
sb.append(" ");
sb.append(list.get(i));
}
int leftSpace = maxWidth - sb.length();
getSpace(leftSpace, sb);
res.add(sb.toString());
return res;
}
private String getSpace(int eachIntervalSpace, StringBuilder sb) {
for (int i = 0; i < eachIntervalSpace; i++) {
sb.append(" ");
}
return sb.toString();
}
}readable version
T: O(w*(n+s)), w is words array size, n is list data size, s is space cnt
S: O(maxWidth* rows)
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> res = new ArrayList<>();
List<String> list = new ArrayList<>();
int len = 0;
for (String word : words) {
// notice here: &&
// ็ถ list ๆ่ณๆ ไธ่ถ
ๅบ maxWidthๆ, ๆ line string ๅ ๅ
ฅๅฐ res, ๆ list, len ้ๆฐๅๅง
if (list.size() != 0 && (len + list.size() + word.length()) > maxWidth) {
String lineStr = getLineStr(list, len, maxWidth); // ๅๅบ line string
res.add(lineStr);
list = new ArrayList<>();
len = 0;
}
// ๅ word ๅฐ list, len้ทๅบฆ
list.add(word);
len += word.length();
}
// last line ๅๅบไพ
String lastStr = getLastLineStr(list, len, maxWidth);
res.add(lastStr);
return res;
}
private String getLineStr(List<String> list, int len, int maxWidth) {
// add to sb
StringBuilder sb = new StringBuilder();
int interval = list.size()-1;
int spaceCnt = maxWidth - len;
// single word case
if (interval == 0) { // list.size() == 1
sb.append(list.get(0));
sb.append(" ".repeat(spaceCnt));
} else { // multi word case
int eachSpaceCnt = spaceCnt/interval;
int extraSpaceCnt = spaceCnt%interval;
String spaceStr = " ".repeat(eachSpaceCnt); //
sb.append(list.get(0));
for (int i = 1; i < list.size(); i++) {
sb.append(spaceStr);
if (extraSpaceCnt > 0) {
sb.append(" ");
extraSpaceCnt--;
}
sb.append(list.get(i));
}
}
return sb.toString();
}
private String getLastLineStr(List<String> list, int len, int maxWidth) {
StringBuilder last = new StringBuilder();
last.append(list.get(0));
for (int i = 1; i < list.size(); i++) {
last.append(" ");
last.append(list.get(i));
}
// notice here: maxWidth - sb.length()
String remainSpaceStr = " ".repeat(maxWidth - sb.length());
last.append(remainSpaceStr);
return last.toString();
}
}
/*
Extra spaces between words should be distributed as evenly as possible.
for not evenly between words,
single space, left more space
the empty slots on the left will be assigned more spaces than the slots on the right.
last line of text, it should be left-justified, no extra space is inserted between words.
["This", "is", "an", "example", "of", "text", "justification."]
cur len 10 , if curlen + next > 16 => next line
4 + 1 +2 + 1 + 2 + |
7
18
list res: result
two variable: list, to save words in curr line, len is words' len
for (all words) {
// only add word to list, len
// pre total length + all pre empty(1 space) + curr Word len <= maxWidth
if (list isEmpty ||len + list.size() + currWord.len <= maxWidth) // list.size() means at least number of space
else { // process line data, add line data to res, add word to list, len
int interval = list.size() -1;
int spaceCnt = maxWidth - len / interval;
int extraSpaceCnt = (maxWidth - len) & interval
String space = ...
String sb = ""
sb.append(list[0])
for (list from 1)
sb.append(space)
sb.append(" ")
extraSpaceCnt--
sb.append(list)
}
res.add(sb)
list = new list
len = 0
list.add(word)
}
handle last line
*/another style
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
int wordLen = 0;
int i = 0;
List<String> result = new ArrayList<>();
List<String> line = new ArrayList<>();
while (i < words.length) {
while (i < words.length && wordLen + words[i].length() + line.size() <= maxWidth) {
line.add(words[i]);
wordLen += words[i].length();
i++;
}
if (i != words.length) {
String eachLine = getLineStr(line, maxWidth, wordLen);
result.add(eachLine);
} else {
String lastLine = getLastLineStr(line, maxWidth, wordLen);
result.add(lastLine);
}
line = new ArrayList<>();
wordLen = 0;
}
return result;
}
private String getLineStr(List<String> line, int maxWidth, int wordLen) {
int spaceCnt = line.size() - 1;
int spaceTotalLen = maxWidth - wordLen;
StringBuilder sb = new StringBuilder();
if (line.size() == 1) {
sb.append(line.get(0));
addSpace(sb, spaceTotalLen);
return sb.toString();
}
// make sure spaceCnt is not zero
int spaceUnitLen = spaceTotalLen/spaceCnt;
int leftSpace = spaceTotalLen%spaceCnt;
sb.append(line.get(0));
for (int i = 1; i < line.size(); i++) {
addSpace(sb, spaceUnitLen);
if (leftSpace > 0) {
addSpace(sb, 1);
leftSpace--;
}
sb.append(line.get(i));
}
return sb.toString();
}
private void addSpace(StringBuilder sb, int cnt) {
for (int i = 0; i < cnt; i++) {
sb.append(" ");
}
}
/*
For the last line of text, it should be left-justified, and no extra space is inserted between words.
*/
private String getLastLineStr(List<String> line, int maxWidth, int wordLen) {
StringBuilder sb = new StringBuilder();
if (line.size() == 1) {
sb.append(line.get(0));
addSpace(sb, maxWidth - wordLen);
return sb.toString();
}
sb.append(line.get(0));
for (int i = 1; i < line.size(); i++) {
addSpace(sb, 1);
sb.append(line.get(i));
}
int leftSpace = maxWidth - wordLen - line.size() + 1; // spaceCnt = line.size() - 1
for (int i = 0; i < leftSpace; i++) {
addSpace(sb, 1);
}
return sb.toString();
}
}Last updated
