6ms fastest Java code beats 99.92%, expected running time O(k),k=number of words, Independent of the number of chars. Independent of the number of rows in most cases.


  • 1
    Y
    public class Solution {
        public int wordsTyping(String[] sentence, int rows, int cols) {
            int s_words=sentence.length,total_char=0;
            int[] word_lengths=new int[s_words];
            int[] word_next=new int[s_words];
            
            for(int i=0;i<s_words;i++){
                word_lengths[i]=sentence[i].length();
                total_char+=word_lengths[i];
            }
            //calculate residue char numbers perline 
            int num_s_pline=cols/(total_char+s_words);
            int res_pline=cols%(total_char+s_words);
            if(res_pline==(total_char+s_words-1)){
                res_pline=0;
                num_s_pline++;
            }
            //calculate first word starting the next line O(k),k: the number of words.
            int head=0,tail=0,sum=0,temp=0;
            while(head<s_words){
                temp=sum+word_lengths[tail];
                if(temp<=res_pline){
                    sum=temp+1;
                    tail=(tail+1)%s_words;
                }
                else{
                    word_next[head]=tail;
                    sum=sum-(word_lengths[head++]+1);
                }
            }
            //calculate total sentences in the residues, if the number of rows is large and have loops, the running time is O(1).
            int k=0,i=0,num_sentences=0;;
            for(k=0;k<rows;k++){
                if(word_next[i]==i) break;
                if(word_next[i]<i) num_sentences++;  
                i=word_next[i];
                if(i==0) break;
            }
            if(i==0){
                int ns=rows/(k+1);
                int nr=rows%(k+1);
                num_sentences=num_sentences*ns;
                for(k=0;k<nr;k++){
                    if(word_next[i]==i) break;
                    if(word_next[i]<i) num_sentences++;  
                    i=word_next[i];
                }
            }
            return num_sentences+num_s_pline*rows;
        }
    }
    

Log in to reply
 

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