# 14ms Java solution by remembering ending index

• A solution by remembering the ending column of the sentence. Whenever we encounter a same column, we found a cycle - and we can calculate the remaining number of times.

public int wordsTyping(String[] sentence, int rows, int cols) {
int count = 0;
int i=0, j=0; // row, col
int[] ends = new int[cols + 1]; // where sentence ends
int[] counts = new int[rows]; // # of times, cumulative
int k = 0;
while (i < rows) {
j += sentence[k].length();
if (j > cols) { // too long, record # of times, go to next row
j = 0;
counts[i] = count;
i++;
k--;
} else {
j++;
}
if (k == sentence.length -1) {
k = 0;
count++;
int row = ends[j-1];
if (row != 0) {
// we have ended in this column before
// important to observe that, from this point onward, end index always repeats
// when we get here, we will know result right away
int rowdiff = i - row; // # of rows in a cycle
int countdiff = counts[i-1] - counts[row-1]; // # of times in a cycle
count += (rows - i - 1) / rowdiff * countdiff; // A
i += (rows - i - 1) / rowdiff * rowdiff; // B
count += counts[row + rows - i - 1] - counts[row-1] - 1; // C
break;
} else {
ends[j-1] = i;
}
} else {
k++;
}
}
return count;
}

A illustrative example: ["w","gn","f","n","jnolzux","cjxqnijs","das","ja","pyexahzx","rwiy"], 13, 200

The first time a sentence ends at a same column happens in row 6 (with row 2), forming a "cycle" - so that we know row 6 to row 10 will be another cycle, and we can add the number of times in cycles (A), and jump to row 10 (B). The remaining doesn't form a full cycle, but we know it will be same as counting the first several rows in a cycle (C). We have only 13 rows in this example, but if it had 1000 rows, line A and B will allow us to jump forward many cycles.

This solution is around 14ms. It doesn't look like a DP solution to me.

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