12ms Java solution with comments, easy to read

  • 0

    The basic idea is using DP to store the number of words contained in a row starting from sentence[i], where sentence[i] is the i'th word in sentence. I was inspired by my friend that we can use modular arithmetic to speed up in case of "#cols >> #word in sentence", like "sentence=["a"],rows=20000,cols=20000", and here is the code:

    public class Solution {
        public int wordsTyping(String[] sentence, int rows, int cols) {
            //the number of words contained in a row starting from sentence[i]
            int[] curRowNum = new int[sentence.length];
            String s = String.join(" ", sentence) + " ";
            // number of whole sentences in a row, used to speed up in case of "#cols >> #word in sentence" 
            int numOfSens = cols/s.length();
            // the remain space for the rest part of the sentence
            int mod = cols%s.length();
            for(int i=0;i<sentence.length;i++){
                int remain = mod;
                curRowNum[i]+=numOfSens*sentence.length;//how many whole sentences here
                int p = i;//p is the starting word index 
            int sumWordNum = 0;//the total number of words
            int start = 0;//start is the starting word index of next row
                sumWordNum += curRowNum[start];
                start = (start+curRowNum[start])%sentence.length;
            return sumWordNum/sentence.length;

Log in to reply

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