Sentence Screen Fitting

Posted on Edited on In Word count in article: 346 Reading time ≈ 1 mins.

Introduction

418. Sentence Screen Fitting

Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.

Note:

A word cannot be split into two lines. The order of words in the sentence must remain unchanged. Two consecutive words in a line must be separated by a single space. Total words in the sentence won’t exceed 100. Length of each word is greater than 0 and won’t exceed 10. 1 ≤ rows, cols ≤ 20,000.

Example: 

1
2
3
4
5
6
7
8
9
10
11
12
13
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.

Solution

Failed Solution

This method is intuitive and solve the problem but exceeds time limit for example like ["a", 20000, 20000] as it uses words in sentence to scan all positions in all rows and columns.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public int wordsTyping(String[] sentence, int rows, int cols) {
  int x = 0, y = 0, i = 0, len = sentence.length;
  int[] words = new int[len];
  // Return 0 immediately if word length exceeds columns.
  for(int m=0; m<len; m++) {
    int length = sentence[m].length();
    if(length > cols) return 0;
    words[m] = length;
  }

  while(y<rows) {
    int wlength = words[i % len];
    if(wlength > cols - x) {
      x = 0;
      y++;
    }
    if(y == rows) break;
    // Add dash sign between words except x when reaches end of row.
    x += wlength;
    if(x < cols) x++;
    i++;
  }
  return i / len;
}

Improved Solution

This method concatenates all words into a long string and use the last column to match the position start % l in long string. If current position is empty char, then all words before position start % l is matched in current row, otherwise move back to the last previous empty char.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int wordsTyping(String[] sentence, int rows, int cols) {
  String s = String.join(" ", sentence) + " ";
  int start = 0, l = s.length();
  for(int i=0; i<rows; i++) {
    start += cols;
    if(s.charAt(start % l) == ' ') {
      start++;
    }
    else {
      while(start > 0 && s.charAt((start-1) % l) != ' ') {
        start--;
      }
    }
  }
  return start / l;
}