# Java solution based on repeat pattern 15ms

• Since the column size is fixed, there is a pattern for each starting word to fit the sentence into one column. For example, when fit ["I", "am", "good" ] to column size of 5:
when starting with "I", it always fills the column with "I-am-" and has next word "good"
when starting with "good", it always fills the column with "good-" and next word is "I"
and keep repeating.
Since "good" is the last word, when "good" is put into a column, the count of the sentence increase by one.
When the column size greater than the length of the whole sentence "I-am-good-", we can increase the count by column size divided by the sentence length.

Time complexity O(n * min(n,rows)), where n is the number of words.

29ms

``````public class Solution {
Map<Integer, Integer> mem = new HashMap();
int count(int idx, int[] lens, int sentence_len, int cols){
int key = idx;
if (mem.containsKey(key)) return mem.get(key);
int repeat = cols/sentence_len;
cols %= sentence_len;
while (cols >= lens[idx]){
if (idx==lens.length-1) repeat++;
cols -= lens[idx]+1;
idx= (idx+1) % lens.length;
}
int ret = repeat * 100 + idx;
mem.put(key, ret);
return ret;
}
public int wordsTyping(String[] sentence, int rows, int cols) {
int[] lens = new int[sentence.length];
int total = 0;
for (int i=0; i<sentence.length; i++) {
lens[i] = sentence[i].length();
total += lens[i]+1;
}
int res = 0, idx = 0;
for (int i=0; i<rows; i++){
int ret = count( idx, lens, total, cols);
idx = ret%100;
res += ret/100;
}
return res;
}
}
``````

15ms version by replacing HashMap with an array.

``````public class Solution {
int[][] mem;
int[] count(int idx, int[] lens, int sentence_len, int cols){
int key = idx;
if (mem[key] != null ) return mem[key];
int repeat = cols/sentence_len;
cols %= sentence_len;
while (cols >= lens[idx]){
if (idx==lens.length-1) repeat++;
cols -= lens[idx]+1;
idx= (idx+1) % lens.length;
}
mem[key] = new int[]{repeat, idx};
return mem[key];
}
public int wordsTyping(String[] sentence, int rows, int cols) {
int[] lens = new int[sentence.length];
mem = new int[sentence.length][];
int total = 0;
for (int i=0; i<sentence.length; i++) {
lens[i] = sentence[i].length();
total += lens[i]+1;
}
int res = 0, idx = 0;
for (int i=0; i<rows; i++){
int[] ret = count( idx, lens, total, cols);
idx = ret[1];
res += ret[0];
}
return res;
}
}
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.