Java, 170 ms.


  • 1
    I

    Idea is to accelerate the process if you have found x sentences occupies the whole y rows, then you know you can skip counting all rows/y*x sentences. I could not come up this idea during contest, terrified by the 'Hard' tag, or probably because of the bad time schedule for eastern area!!!!!!!!!

    public int wordsTyping(String[] sentence, int rows, int cols) {
        int ans = 0, len = 0;
        for (int i = 0; i < sentence.length; ++i) {
            if (sentence[i].length() > cols) return ans;
            len += sentence[i].length() + 1;
        }
        for (int i = 0, j = 0; i < rows;) {
            if (j + len <= cols + 1) {
                j += len;
                if (j >= cols) {
                    j = 0;
                    i++;
                }
            } else {
                for (int k = 0; k < sentence.length; ++k) {
                    j += sentence[k].length() + 1;
                    if (j > cols + 1) {
                        j = sentence[k].length() + 1;
                        i++;
                    } else if (j >= cols) {
                        j = 0;
                        i++;
                    }
                }
            }
            if (i > rows || i == rows && j > 0) break;
            ans++;
            if (j == 0) {
                ans *= rows / i;
                i *= rows / i;
            }
        }
        return ans;
    }
    

Log in to reply
 

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