Sentence Screen Fitting ใน C++ : นับจำนวนครั้งที่วางประโยคบนหน้าจอได้

ให้หน้าจอขนาด rows x cols และ **Sentence** (Array ของ Words) หาว่า **วางประโยคซ้ำได้กี่รอบเต็ม** ตามกติกา:

• Word **ไม่ตัดข้ามบรรทัด** (ต้องอยู่บรรทัดเดียวกันหมด)
• ลำดับ Word **ต้องคงเดิม** วนซ้ำ
• Word ระหว่างกัน **เว้น Space 1 ช่อง**

ตัวอย่าง

rows=3, cols=6, sentence=["a", "bcd", "e"]

Row 1: "a bcd "  (len 1+1+3=5, next "e" ไม่เข้า cols=6)
Row 2: "e a   "  (len 1+1+1=3, next "bcd" ไม่เข้า)
Row 3: "bcd e "  (len 3+1+1=5)
Total words placed: 8 words = 2 full sentences (3 words/sentence)
Output: 2

แนวทาง: DP + Cycle Detection (Memoization per Row Start)

State: startWordIndex (Word ที่เริ่มบรรทัดนี้) -> wordsPlacedInThisRow

1. Memoize: dp[start] = count จำนวน Words ที่วางได้ใน Row ที่เริ่มที่ Word start
2. Simulate Row โดย Row:
   • start = totalWordsPlaced % n
   • ถ้า dp[start] คำนวณแล้ว -> ใช้ค่าเก้า
   • Else -> Simulate วาง Word ใน Row นี้ จนกว่าเข้าไม่ได้ -> เก็บ dp[start]
3. รวม totalWordsPlaced ทุก Row -> คำตอบ = totalWordsPlaced / n

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

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int wordsTyping(vector<string>& sentence, int rows, int cols) {
        unordered_map<int, int> dp; // startWordIndex -> wordsFittedInRow
        int totalWords = 0;
        int n = sentence.size();

        while (rows--) {
            int start = totalWords % n;
            if (!dp.count(start)) {
                int len = -1; // -1 เพราะ word แรกไม่มี space นำหน้า
                int cnt = 0;
                // Pack words in this row
                while (1 + len + sentence[(start + cnt) % n].size() <= cols) {
                    len = 1 + len + sentence[(start + cnt) % n].size();
                    cnt++;
                }
                dp[start] = cnt;
                totalWords += cnt;
            } else {
                totalWords += dp[start];
            }
        }
        return totalWords / n;
    }
};

Input / Output

Input:  ["a","bcd","e"] 3 6
Output: 2

ความซับซ้อน (Complexity)

• Time: O(Rows * AvgWordsPerRow) แต่ด้วย Memoization จริงๆ ~ O(N * Cols) หรือ O(Rows + N*AvgWordLen) เร็วมาก
• Space: O(N) — DP Map Size = จำนวน Word (≤ 100)

จุดสำคัญ

• len = -1 Trick: ทำให้ Word แรกไม่ต้องบวก Space
• Modulo n จัดการการวน Sentence อัตโนมัติ
• DP Key = startWordIndex เพราะ State ของ Row ขึ้นกับ Word เริ่มต้นอย่างเดียว

วิธีนี้หลีกเลี่ยงการ Simulate ทุก Character ได้อย่างสวยงามครับ