418. Sentence Screen Fitting
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.
1 public class Solution { 2 public int wordsTyping(String[] sentence, int rows, int cols) { 3 String s = String.join("_", sentence) + "_"; 4 int len = s.length(); 5 int count = 0; 6 int[] map = new int[len]; 7 for (int i = 1; i < len; ++i) { 8 // if charAt(i) == '_', which means we saved an extra space 9 map[i] = s.charAt(i) == '_' ? 1 : map[i-1] - 1; 10 } 11 for (int i = 0; i < rows; ++i) { 12 count += cols; 13 count += map[count % len]; 14 } 15 return count / len; 16 } 17 }
1 public int wordsTyping(String[] sentence, int rows, int cols) { 2 String s = String.join(" ", sentence) + " "; 3 int start = 0; 4 int length = s.length(); 5 for (int i = 0; i < rows; i++) { 6 start += cols; 7 if (s.charAt(start % length) == ' ') { 8 start++; 9 } else { 10 while (start >= 0 && s.charAt(start % length) != ' ') { 11 start--; 12 } 13 start++; 14 } 15 } 16 17 return start / length; 18 }
浙公網安備 33010602011771號