Word Wrap Problem (จัดรูปแบบข้อความให้สมดุล)

กำหนดลำดับคำ (words) และความกว้างสูงสุดของบรรทัด (maxWidth) ต้องการจัดบรรทัด (Word Wrap) ให้ **สมดุลที่สุด** คือ minimize sum of squares ของ extra spaces ในแต่ละบรรทัด (ยกเว้นบรรทัดสุดท้าย)

ตัวอย่าง Input และ Output

Word lengths: {3, 2, 2, 5}
Max width: 6

Output:
Line 1: Word 1 to 1 (คำที่ 1 อย่างเดียว "xxx" → 3 spaces extra)
Line 2: Word 2 to 3 (คำที่ 2-3 "xx xx" → 2+1+2=5, 1 space extra)
Line 3: Word 4 to 4 (คำที่ 4 "xxxxx" → 5, 1 space extra)

Cost = 3² + 1² + 0² = 10 (last line cost = 0)

อัลกอริทึม Dynamic Programming

ฟังก์ชัน wordWrap(wordLenArr, size, maxWidth)

กำหนด:

• extraSpace[i][j] = ช่องว่างเหลือ หากวางคำ i ถึง j ในบรรทัดเดียว
• lineCost[i][j] = ค่าใช้จ่ายของบรรทัด (extraSpace², หรือ 0 ถ้าบรรทัดสุดท้าย, หรือ INF ถ้าวางไม่ได้)
• totalCost[j] = minimum cost สำหรับคำ 1 ถึง j
• solution[j] = ตำแหน่งเริ่มต้นของบรรทัดสุดท้ายสำหรับคำ 1..j

ขั้นตอน:

1. คำนวณ extraSpace[i][j]:
   • extraSpace[i][i] = maxWidth - wordLenArr[i-1]
   • extraSpace[i][j] = extraSpace[i][j-1] - wordLenArr[j-1] - 1 (ลบความยาวคำ + 1 space)
2. คำนวณ lineCost[i][j]:
   • ถ้า extraSpace < 0 → INF
   • ถ้า j == size && extraSpace >= 0 → 0 (บรรทัดสุดท้าย)
   • มิฉะนั้น → extraSpace²
3. DP หา totalCost:
   • totalCost[0] = 0
   • for j = 1..size: totalCost[j] = min over i (totalCost[i-1] + lineCost[i][j])
   • เก็บ solution[j] = i ที่ให้ค่าต่ำสุด
4. Trace back จาก solution[size] เพื่อพิมพ์การจัดบรรทัด

ตัวอย่างโค้ด C++

#include <iostream>
#include <climits>
#include <algorithm>
using namespace std;

int dispSolution(int solution[], int size) {
    int k;
    if (solution[size] == 1) k = 1;
    else k = dispSolution(solution, solution[size]-1) + 1;
    cout << "Line number " << k << ": Word Number: " 
         << solution[size] << " to " << size << endl;
    return k;
}

void wordWrap(int wordLenArr[], int size, int maxWidth) {
    int extraSpace[size+1][size+1];
    int lineCost[size+1][size+1];
    int totalCost[size+1];
    int solution[size+1];

    // extraSpace
    for(int i = 1; i <= size; i++) {
        extraSpace[i][i] = maxWidth - wordLenArr[i-1];
        for(int j = i+1; j <= size; j++)
            extraSpace[i][j] = extraSpace[i][j-1] - wordLenArr[j-1] - 1;
    }

    // lineCost
    for (int i = 1; i <= size; i++) {
        for (int j = i; j <= size; j++) {
            if (extraSpace[i][j] < 0) lineCost[i][j] = INT_MAX;
            else if (j == size && extraSpace[i][j] >= 0) lineCost[i][j] = 0;
            else lineCost[i][j] = extraSpace[i][j] * extraSpace[i][j];
        }
    }

    // DP
    totalCost[0] = 0;
    for (int j = 1; j <= size; j++) {
        totalCost[j] = INT_MAX;
        for (int i = 1; i <= j; i++) {
            if (totalCost[i-1] != INT_MAX && lineCost[i][j] != INT_MAX &&
                totalCost[i-1] + lineCost[i][j] < totalCost[j]) {
                totalCost[j] = totalCost[i-1] + lineCost[i][j];
                solution[j] = i;
            }
        }
    }
    dispSolution(solution, size);
}

int main() {
    int wordLenArr[] = {3, 2, 2, 5};
    int n = 4, maxWidth = 6;
    wordWrap(wordLenArr, n, maxWidth);
    return 0;
}

Output

Line number 1: Word Number: 1 to 1
Line number 2: Word Number: 2 to 3
Line number 3: Word Number: 4 to 4

ความซับซ้อน

• Time: O(n²)
• Space: O(n²)

การประยุกต์

ใช้ใน Text Editors, Word Processors, LaTeX, และ Code Formatters