Leetcode: Sentence Screen Fitting

发布时间:2017-6-29 1:24:37 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"Leetcode: Sentence Screen Fitting ",主要涉及到Leetcode: Sentence Screen Fitting 方面的内容,对于Leetcode: Sentence Screen Fitting 感兴趣的同学可以参考一下。

Given a rows x cols screen and a sentence represented by a list of 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 won't exceed 10.1 ≤ rows, cols ≤ 20,000.Example 1:Input:rows = 2, cols = 8, sentence = ["hello", "world"]Output: 1Explanation:hello---world---The character '-' signifies an empty space on the screen.Example 2:Input:rows = 3, cols = 6, sentence = ["a", "bcd", "e"]Output: 2Explanation: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: 1Explanation:I-hadapplepie-Ihad--The character '-' signifies an empty space on the screen.

先来一个brute force, 类似Text Adjustment

 1 public class Solution { 2     public int wordsTyping(String[] sentence, int rows, int cols) { 3         if (sentence==null || sentence.length==0 || sentence.length>rows*cols || rows<=0 || cols<=0) 4             return 0; 5         int res = 0; 6         int j = 0; //indicate the index of string in sentence that is currently trying to be inserted to current row 7         int row = 0; //current row 8         int col = 0; //current col 9         10         while (row < rows) {11             while (col + sentence[j].length() - 1 < cols) {12                 col = col + sentence[j].length() + 1;13                 j++;14                 if (j == sentence.length) {15                     res++;16                     j = 0;17                 }18             }19             row++;20             col = 0;21         }22         return res;23     }24 }

但是在稍微大一点的case就TLE了,比如:

["a","b","e"] 20000 20000, 花了465ms

所以想想怎么节约时间,

提示是可以DP的,想想怎么复用,refer to: https://discuss.leetcode.com/topic/62364/java-optimized-solution-17ms

如果这一行由sentence里面某一个string开头,那么,下一行由哪个string开头,这个是确定的;同时,本行会不会到达sentence末尾,如果会,到几次,这个也是一定的

这两点就可以加以利用,因为我们找到了DP的复用关系

sub-problem: if there's a new line which is starting with certain index in sentence, what is the starting index of next line (nextIndex[]). BTW, we compute how many times the pointer in current line passes over the last index (times[]).

Time complexity : O(n*(cols/lenAverage)) + O(rows), where n is the length of sentence array, lenAverage is the average length of the words in the input array.

 1 public class Solution { 2     public int wordsTyping(String[] sentence, int rows, int cols) { 3         int[] nextInt = new int[sentence.length]; 4         int[] times = new int[sentence.length]; 5         for (int i=0; i<sentence.length; i++) { 6             int cur = i; //try to insert string with index cur in sentence to current row 7             int col = 0; //current col 8             int time = 0; 9             while (col + sentence[cur].length() - 1 < cols) {10                 col = col + sentence[cur++].length() + 1;11                 if (cur == sentence.length) {12                     cur = 0;13                     time++;14                 }15             }16             nextInt[i] = cur;17             times[i] = time;18         }19         20         int res = 0;21         int cur = 0;22         for (int i=0; i<rows; i++) {23             res += times[cur];24             cur = nextInt[cur];25         }26         return res;27     }28 }

上一篇:Maven最佳实践:划分模块
下一篇:AES对称加密util

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。