7ms Java solution


  • 0
    M
    public int wordsTyping(String[] sentence, int rows, int cols) {
        int n = sentence.length;
        if(n == 0) return 0;
    
        int sentenceChars = 0; // total # of chars that a sentence occupies, including spaces
        for(String w: sentence)
            sentenceChars += w.length() + 1;
    
        int[] lineWords = new int[n]; // # of words that can fit one a line, where the line starts with the word at that index
        int remainingChars = cols % sentenceChars; // # of chars remaining in each row after filling in complete sentences
        for(int l = 0, r = -1, c = -1; l < 2 * n && r < 2 * n;){
            if(c > remainingChars){
                c -= sentence[r-- % n].length() + 1;
                lineWords[l % n] = r - l + 1;
                c -= sentence[l++ % n].length() + 1;
            } else {
                c += sentence[++r % n].length() + 1;
            }
        }
    
        int[] lines = new int[n];
        int startingWord = 0, lineCount = 0;
        Map<Integer,Integer> seenWords = new HashMap<>();
        
        for(; !seenWords.containsKey(startingWord); lineCount++){
            seenWords.put(startingWord, lineCount);
            lines[lineCount] = (lineCount > 0 ? lines[lineCount - 1] : 0) + lineWords[startingWord];
            startingWord = (startingWord + lineWords[startingWord]) % n;
        }
        int cycleStart = seenWords.get(startingWord);
        int cycleLines = lineCount - cycleStart;
        int headLines = Math.min(rows, cycleStart);
        int headWords = headLines > 0 ? lines[headLines - 1] : 0;
        int tailLines = rows - headLines;
        int words = headWords + tailLines / cycleLines * (lines[lineCount - 1] - headWords);
        int remainingLines = tailLines % cycleLines;
        if(remainingLines > 0)
            words += lines[cycleStart + remainingLines - 1] - headWords;
        words += cols / sentenceChars * n * rows;
    
        return words / n;
    }

Log in to reply
 

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