99% 0ms O(n) c++ solution where n = #words. Detailed explanation and analysis included.


  • 6
    J

    Sorry for the ugly code, not sure how to make it cleaner. Here are the key points being used to make it O(n).

    1. When cols is really large, find length of a complete sentence and shrink cols to a smaller size.
      i). For example: cols = max( 0, ((cols+1)%(length+1))-1 ); This takes O(n) time.
      ii). Also, keep track of numSentenceInRow = (cols+1)/(total+1);.

    2. Build a DP table, where DP[i]=j means that if a line start with the ith word, then the next line will start with the jth word. Using a sliding window approach, this will take O(n) time, sincecols is now <length.

    3. Finally to handle large rows, we will use DP table to find the period where the first word start repeating.
      i). For example, the pattern may look like this 0->7->4->1->8->5->2->8->5->2... O(n) time since cycle cannot be longer than n.
      ii) Shrink the number of rows to newRows as follows:
      if( rows > n ) {
      newRows = (rows-n)%period + n;
      numCycle = (rows-n)/period;
      }

    4. Compute the number of sentences in each cycle and in the first newRows. O(n) time since newRows<2*n.
      Total = numCycle*numSentenceInCycle + numSentence + rows*numSentenceInRow

    My ugly code...

    class Solution {
        vector<int> dp, visited;
    public:
        int wordsTyping(vector<string>& sentence, int rows, int cols) {
            int total = -1, n = sentence.size();
            dp = vector<int>( 2*n , 0 );
            visited = vector<int>( 2*n , -1 );
            
            //if cols is too large, check for cycle and shrink it
            for( auto w: sentence ) total += w.size() + 1;
            int numSentenceInRow = (cols+1)/(total+1);
            cols = max( 0, ((cols+1)%(total+1))-1 );
    
            //build dp table using sliding window for o(n) performance
            total = -1;
            int j = 0;
            for( int i = 0; i< n*2; i ++){
                int k = i%n;
                while( total + 1 + (int)sentence[k].size() > cols ){
                    dp[j%n] = k;
                    total = total - ( 1 + sentence[(j++)%n].size() ) ;
                }
                total += (1 + sentence[k].size());
            }
    
            //find cycle
            int curr = 0, i = 0, count = 0;
            while( visited[curr] == -1 ){
                visited[curr] = i++;
                curr = dp[curr];
            }
            int period = i-visited[curr], start = curr;
            int newRows = rows, numCycle = 0;
            
            //if rows is too large, check for cycle and shrink it
            if( rows > n ) {
                newRows = (rows-n)%period + n;
                numCycle = (rows-n)/period;
            }
            
            //count number of sentence in each cycle o(n)
            int numSentenceInCycle = dp[start] < start;
            curr = dp[start];
            while( curr != start ){
                if( dp[curr] < curr ) numSentenceInCycle ++;
                curr = dp[curr];
            }
            
            //count number of sentence in first few lines o(n)
            int numSentence = 0;
            curr = 0;
            for( int m = 0; m < newRows; m ++){
                if( dp[curr] < curr ) numSentence ++;
                curr = dp[curr];
            }
            return numCycle*numSentenceInCycle + numSentence + rows*numSentenceInRow;
        }
    };
    

  • 0

    Nice solution! I have one question: while shrinking the number of rows, why do (rows - n)? Thanks.


  • 0
    J

    Let p = period, I think sometimes, the pattern doesn't appear within the first p lines, for example
    0->7->4->1->8->5->2->8->5->2...
    I am doing that to make sure that there are enough rows for the pattern to appear.


  • 0
    G

    dp = vector<int>( n , 0 ); is what's required. I think the 2*n was there only due to historical reason. Good solution!


Log in to reply
 

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