สมมติว่าเรามีอาร์เรย์ของคำและความกว้าง maxWidth เราต้องจัดรูปแบบข้อความให้แต่ละบรรทัดมีตัวอักษรพอดี maxWidth ตัวและจัดเต็มทั้งสองข้าง (fully justified) เราควรจัดคำแบบ greedy คือ ใส่คำให้มากที่สุดในแต่ละบรรทัด เราจะเติมช่องว่างเพิ่มเติมเมื่อจำเป็น เพื่อให้แต่ละบรรทัดมีตัวอักษรพอดี maxWidth ตัว
ช่องว่างเพิ่มเติมระหว่างคำควรกระจายให้เท่าที่สุดเท่าที่จะเป็นไปได้ ถ้าจำนวนช่องว่างในบรรทัดหารไม่ลง ช่องว่างทางซ้ายจะได้รับช่องว่างมากกว่าด้านขวา สำหรับบรรทัดสุดท้ายของข้อความ ควรจัดชิดซ้าย (left justified) และไม่แทรกช่องว่างเพิ่มระหว่างคำ
ขั้นตอนการแก้ปัญหา
- สร้างอาร์เรย์ result
- for i ในช่วง 0 ถึงขนาดของ a อัปเดต i ด้วย j
- width := 0
- for j ในช่วง i ถึงขนาดของ a และ width + ขนาดของ a[j] + j – i <= b
- width := width + ขนาดของ a[j]
- space := 1, extra := 0
- ถ้า j – 1 != 1 และ j != ขนาดของ a
- space := (b - width) / (j - i - 1)
- extra := (b - width) mod (j - i - 1)
- line := a[i]
- for k ในช่วง i + 1 ถึง j
- ต่อช่องว่างจำนวน space เข้ากับ line
- ถ้า extra > 0 ต่อช่องว่างเพิ่มเข้าไป
- ลด extra ลง 1
- line := ต่อ a[k] เข้ากับ line
- x := ขนาดของ line
- line := ต่อช่องว่าง (b - x) ตัวเข้ากับ line
- ใส่ line ลง result
- คืนค่า res
ตัวอย่างโค้ด C++
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i < v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
vector<string> fullJustify(vector<string> &a, int b) {
vector<string> result;
int i, j;
for(i = 0; i < a.size(); i = j){
int width = 0;
for(j = i; j < a.size() && width + a[j].size() + j - i <= b; j++){
width += a[j].size();
}
int space = 1;
int extra = 0;
if(j - i != 1 && j != a.size()){
space = (b - width) / (j - i - 1);
extra = (b - width) % (j - i - 1);
}
string line(a[i]);
for(int k = i + 1; k < j; k++){
line += string(space, ' ');
if(extra-- > 0){
line += " ";
}
line += a[k];
}
int x = line.size();
line += string(b - x, ' ');
result.push_back(line);
}
return result;
}
};
int main(){
vector<string> v = {"I", "love", "coding.", "here", "we", "will", "write", "some", "program"};
Solution ob;
print_vector(ob.fullJustify(v, 16));
}อินพุต
["I", "love", "coding.", "here", "we", "will", "write", "some", "program"] 16
เอาต์พุต
[I love coding., here we will, write some, program , ]
