14ms Java solution by remembering ending index


  • 0
    Y

    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

    0_1478839500807_Screen Shot 2016-11-10 at 11.31.11 PM.png

    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.


Log in to reply
 

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