12ms Java solution with comments, easy to read


  • 0
    Z

    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 
                while(remain-sentence[p].length()>=0){
                    remain=remain-sentence[p].length()-1;
                    curRowNum[i]++;
                    p=(p+1)%(sentence.length);
                }
            }
            int sumWordNum = 0;//the total number of words
            int start = 0;//start is the starting word index of next row
            while(rows>0){
                sumWordNum += curRowNum[start];
                start = (start+curRowNum[start])%sentence.length;
                rows--;
            }
            return sumWordNum/sentence.length;
        }
    }
    

Log in to reply
 

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