LeetCode-68.文本左右對齊（相關話題：字元串）
給定一個單詞數組和一個長度 maxWidth，重新排版單詞，使其成為每行恰好有 maxWidth 個字元，且左右兩端對齊的文本。
你應該使用「貪心演算法」來放置給定的單詞；也就是說，儘可能多地往每行中放置單詞。必要時可用空格 填充，使得每行恰好有 maxWidth 個字元。
要求儘可能均勻分配單詞間的空格數量。如果某一行單詞間的空格不能均勻分配，則左側放置的空格數要多於右側的空格數。
文本的最後一行應為左對齊，且單詞之間不插入額外的空格。
說明:
- 單詞是指由非空格字元組成的字元序列。
- 每個單詞的長度大於 0，小於等於 maxWidth。
- 輸入單詞數組 words 至少包含一個單詞。
示例:
輸入:
words = ["This", "is", "an", "example", "of", "text", "justification."]
maxWidth = 16
輸出:
[
"This is an",
"example of text",
"justification. "
]
示例 2:
輸入:
words = ["What","must","be","acknowledgment","shall","be"]
maxWidth = 16
輸出:
[
"What must be",
"acknowledgment ",
"shall be "
]
解釋: 注意最後一行的格式應為 "shall be " 而不是 "shall be",
因為最後一行應為左對齊，而不是左右兩端對齊。
第二行同樣為左對齊，這是因為這行只包含一個單詞。
示例 3:
輸入:
words = ["Science","is","what","we","understand","well","enough","to","explain",
"to","a","computer.","Art","is","everything","else","we","do"]
maxWidth = 20
輸出:
[
"Science is what we",
"understand well",
"enough to explain to",
"a computer. Art is",
"everything else we",
"do "
]
解題思路：個人未想到特定的演算法適合解決此類問題，按照題目所給要求解題。
利用兩個變數begin和end，[begin, end)表示可放在同一行的單詞的下標起始位置（左閉右開區間），然後判斷是否為一個單詞佔一行或者最後一行，左對齊；否則，左右對齊。
java代碼：
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> res = new LinkedList();
int begin , end = 0;//begin、end為下標，每層for循環中，[begin, end)表示可放在同一行的單詞的下標起始位置
for(int i =0; i< words.length; ) {
begin = end;
//判斷哪些單詞可放在同一行
int sumLen = 0;
while(end < words.length) {
sumLen += (end > begin ? 1 : 0) + words[end].length();
if(sumLen <= maxWidth)
end++;
else
break;
}
//一個單詞佔一行或最後一行，左對齊
if(end == words.length || end == begin+1){
StringBuilder sb = new StringBuilder(maxWidth);
for(int l = begin; l < end; l++){
sb.append(words[l] + " ");
}
sb.deleteCharAt(sb.length()-1);
while(sb.length() < maxWidth){
sb.append(" ");
}
res.add(sb.toString());
} else { //左右對齊
//相鄰單詞之間的空格數
int spaceCnt = (maxWidth - (sumLen - words[end].length()-1))/(end-begin-1) + 1;
int mod = (maxWidth - (sumLen - words[end].length()-1))%(end-begin-1);
StringBuilder sb = new StringBuilder(maxWidth);
for(int l = begin; l < end-1; l++){
sb.append(words[l]);
for(int j = 0; j < spaceCnt; j++)
sb.append(" ");
//空格數不能完全分配時，左側空格數多於右側空格數
if(l-begin < mod)
sb.append(" ");
}
res.add(sb.append(words[end-1]).toString());
}
i = end;
}
return res;
}
}
推薦閱讀：
