0418. Sentence Screen Fitting

https://leetcode.com/problems/sentence-screen-fitting

Description

Given a rows x cols screen and a sentence represented as a list of strings, return the number of times the given sentence can be fitted on the screen.

The order of words in the sentence must remain unchanged, and a word cannot be split into two lines. A single space must separate two consecutive words in a line.

Example 1:

**Input:** sentence = ["hello","world"], rows = 2, cols = 8
**Output:** 1
**Explanation:**
hello---
world---
The character '-' signifies an empty space on the screen.

Example 2:

**Input:** sentence = ["a", "bcd", "e"], rows = 3, cols = 6
**Output:** 2
**Explanation:**
a-bcd- 
e-a---
bcd-e-
The character '-' signifies an empty space on the screen.

Example 3:

**Input:** sentence = ["i","had","apple","pie"], rows = 4, cols = 5
**Output:** 1
**Explanation:**
i-had
apple
pie-i
had--
The character '-' signifies an empty space on the screen.

Constraints:

• 1 <= sentence.length <= 100

• 1 <= sentence[i].length <= 10

• sentence[i] consists of lowercase English letters.

• 1 <= rows, cols <= 2 * 104

ac1: brute force

TLE

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        // edge cases
        if (sentence == null || sentence.length == 0 || rows <= 0 || cols <= 0) 
            return 0;

        int n = sentence.length;
        int s = 0;  // sentence index
        for (int r = 0, c = 0; r < rows; r++) {
            if (sentence[s%n].length() > cols) return 0;  // one word is longer than screen

            while (cols - c >= sentence[s%n].length()) {  // remaining space can fit next word
                c += sentence[s%n].length() + 1;
                s++;
            } 

            c = 0;  // new row, restart
        }

        return s / n;
    }
}

ac2: memorization

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        // edge cases
        if (sentence == null || sentence.length == 0 || rows <= 0 || cols <= 0) 
            return 0;

        int n = sentence.length;
        int[] times = new int[n];
        int[] nextIdx = new int[n];

        for (int i = 0; i < n; i++) {
            int c = 0;  // current column
            int curr = i;  // sentence index
            int time = 0;  // does this line finish one round?
            while (c + sentence[curr].length() <= cols) {  // remaining space can put current word
                c += sentence[curr++].length() + 1;  // one space after, so + 1
                if (curr == n) {  // finish one round, reset to beginning
                    time++;
                    curr = 0;
                }
            }

            nextIdx[i] = curr;  // the begin index for next line
            times[i] = time;
        }

        int res = 0;
        int s = 0;  // index of sentence
        for (int i = 0; i < rows; i++) {
            res += times[s];
            s = nextIdx[s];
        }

        return res;
    }
}

/*
memorization, if row start with sentence[s], what is the times and starting index for next line.
*/