418 Sentence Screen Fitting

Given arows x colsscreen and a sentence represented by a list of words, findhow many timesthe given sentence can be fitted on the screen.

Note:

1. A word cannot be split into two lines.

2. The order of words in the sentence must remain unchanged.

3. Two consecutive words

   in a line

   must be separated by a single space.

4. Total words in the sentence won't exceed 100.

5. Length of each word won't exceed 10.

6. 1 ≤ rows, cols ≤ 20,000.

Example 1:

Input:

rows = 2, cols = 8, sentence = ["hello", "world"]


Output:

1


Explanation:

hello---
world---

The character '-' signifies an empty space on the screen.

Example 2:

Input:

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


Output:

2


Explanation:

a-bcd- 
e-a---
bcd-e-

The character '-' signifies an empty space on the screen.

Example 3:

Input:

rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]


Output:

1


Explanation:

I-had
apple
pie-I
had--

The character '-' signifies an empty space on the screen.

Brute Force

• Learned something interesting this approach. Effectively, its just like using recursion: I can a function on itself a certain amount of times (iteratively), and update the parameters I pass into it. And just like recursion I have a stopping condition. I have found this approach to be a lot more intuitive than using recursion the traditional way.

• The problem was broken down into a smaller subproblems: I look on how many times I can fit into a single row, and iterate through all the rows. This is not the quickest way, but it is definitely quicker than brute force. I suppose an optimization would be using division more effectively along with modulus.

• I return the total_fit, which just gets added to a total of larger scope. In addition, I add the position of the iterator, which will be used on the next run. In pos_end_row_and_amount_fit, I entire that the row size is not exceeded, and add an additional fit once an entire loop of the sentence is iterated through.

//TLE!

pair<int, int> pos_end_row_and_amount_fit(vector<string>& sentence, int cols, int pos_start)
{
    int row_size = cols;
    int num_fit = 0;
    int iter = pos_start;

    while (row_size >= 0 && row_size >= sentence[iter].length()) {
        row_size -= (sentence[iter].length() + 1);
        iter = ++iter % sentence.size();
        if (iter == 0) num_fit++;
    }
    return make_pair(iter, num_fit);
}

int wordsTyping(vector<string>& sentence, int rows, int cols)
{
    int total_fit = 0;
    int pos_start = 0;

    for (int i = 0; i < rows; i++) {
        pair<int, int> next_row = pos_end_row_and_amount_fit(sentence, cols, pos_start);
        total_fit += next_row.second;
        pos_start = next_row.first;
    }

    return total_fit;
}



int main()
{
    vector<string> tests = { "f","p","a" };
    cout << wordsTyping(tests, 8, 7) << endl; // ok

    tests = { "hello", "world" };
    cout << wordsTyping(tests, 2, 8) << endl; // ok

    tests = { "a", "bcd", "e" };
    cout << wordsTyping(tests, 3, 6) << endl; // ok

    tests = { "I", "had", "apple", "pie" };
    cout << wordsTyping(tests, 4, 5) << endl; // ok
}

Now with Dynammic Programming:

The Idea: We take a similiar approach from before except that we store our previously calculations into a map when we already know the answer. The approach goes as follows. Lets operate 1 row at a time, as keep track the total number of words that were fitted. So iterate through the number of rows. For each row, check how many words in the sentence we can fit inside the row starting at the word we left off. Store this into a dictionary. Every row operates independently, so we know that if we have the same word at the start of the row, the number of words that will fit will always be the same. To check how many words fit in a row, continually subtract the length of the next word - 1 (for space), until we reach a point where the number of remaining space in the current row is -2 or fewer. The reason for this is strictly for when I update the times. -1 is acceptable because it implies that the space took the extra space when it already reached the final element of the row.

Complexity: Fluctuates dependent on input parameters. Maybe someone can help me here.

class Solution:
    def wordsTyping(self, sentence, rows, cols):
        """
        :type sentence: List[str]
        :type rows: int
        :type cols: int
        :rtype: int
        """

        if not sentence or not rows or not cols:
            return 0

        def amount_fit_in_row(start, remainder):
            times = 0
            while True:
                remainder = remainder - len(sentence[start]) - 1
                start = (start + 1) % len(sentence)
                if remainder <= -2:
                    return times
                times += 1

        total_fit = 0
        n = len(sentence)
        fitted = {}

        for row in range(0, rows):
            start = total_fit % n
            if start not in fitted:
                fitted[start] = amount_fit_in_row(start, cols)
            total_fit += fitted[start]

        return int(total_fit / n)