Given a list of words, and the number of rows and columns, return the number of words that can be fit into the rows and columns by stringing together each consecutive word. If the next word does not fit in the same line, it should move to the next line. Find an efficient solution for this.
Example:
List of words: {"Do", "Run"}
Number of columns: 9
Number of rows: 2
return 5. First row: "Do Run Do", second row: "Run Do"
给出一个字符串组，和行列数，求最多能放多少个单词。要求单词是按照组里的顺序摆放，单词之间有空格，假如剩余空间放不下，就放到下一行。
1. 询问
上边中文题目有很多都是我自己补充的，题目没有明确说明，但根据那个例子来看是这么个意思。实际面试应该要问清楚是不是这样。
会不会有空字符串？假设没有。会不会有一整行都放不下一个字符串的情况？假设没有。
2. 分析
直接想法
非常直接的想法就是模拟这个过程。首先获得整个组的长度，然后开始一个个放，每次判断剩余空间够不够，同时记录当前单词的index，放完以后再更新。时间复杂度如何计算？就是和放下的单词总数一样，大致是O(MN/L)，其中L是所有字符串的长度之和。因为字符串长度为1也罢，100也罢，算法里面都是一次计算，而长度越大，能放的单词越少，用时也就越少。
如何改进
可以想象上面的解法在遇见{"a"}和M=10000，N=10000的时候会TLE。为什么？因为在可以直接得出结果的时候，就不需要再去模拟过程。
进一步的思想就是，把整个组看成一个单词，加上空格，如果剩余空间够，直接放一个组进去，然后加上对应的单词数；
再进一步，直接用剩余空间判断能放多少个组，一次性放完。这个操作可以看做常数时间。
那就有个问题，假如每一行都刚好差一个单词不能放下整个组怎么办？
假如还是一个个放，最坏情况开始和结束都放k-1个，k是总共的字符串数量，那么一行就是O(k)，总体O(Mk)，空间复杂度O(k)，其实可以做到O(1)。
如果可以获得从任意字符开始，到之后任意字符结束的长度，能很快地根据剩余长度和当前字符，判断可以放哪些，可以用二分查找。
构造这个长度表的复杂度是O(k2)，然后任意一行一定可以分为开始不完全部分+重复的若干完全部分+末尾不完全部分，所谓完全部分就是整个字符组的拼接，开始和末尾当然有可能为空，这个看具体情况。这样就是2个二分，然后完全部分的计算可以视为常数时间。因此总体的时间复杂度是O(k2+Mlogk)，空间复杂度O(k^2)。
具体使用哪一个？可以和面试官讨论，如果时间足够的话。其实主要的trade off就是预先计算的时间和二分查找节省的时间。只有当M>>k的时候，方法二才会更加好。而从实现难易程度来看，方法二更加难写。在有限的时间里面，我更倾向于方法一，然后可以谈一谈方法二。
关键公式
假设一个单词长度为w，之间要有空格，那么长度为p的空间能放下几个这样的单词？
列公式：nw+n-1<=p,n(w+1)<=p+1,n<=(p+1)/(w+1)。
n个单词所占据的空间：n(w+1)-1，剩余空间：p-(n(w+1)-1)。
此外，对刚好放下的字符串的处理，剩余空间还是要多减去1，这样和那种不是刚好放下的情况统一，只需要判断剩余空间的情况就行了。假如对刚好放下做特殊处理，代码会变得复杂
3. 代码
class Solution:
# method 1
def getNumber(self, list, row, col):
if not list:
return 0
count = len(list)
lengthSeq = [len(x) for x in list]
# total length
L = sum(lengthSeq) + count - 1
# cur: current string index; ret: result number; i: current row index
cur = ret = i = 0
space = col
while i < row:
# count how many total length can be inserted
if cur == 0 and (space + 1) // (L + 1) > 0:
n = (space + 1) // (L + 1)
ret += n * count
space -= n * (L + 1) - 1
space -= 1
# insert 1 word if has space
elif space >= lengthSeq[cur]:
space -= lengthSeq[cur] + 1
ret += 1
cur += 1
cur %= count
# else change line
else:
i += 1
space = col
return ret
4. 总结
难度medium~hard，要分析得透彻和写出正确代码，在短短30分钟里面不是很容易的事情。
