418 Sentence Screen Fitting

T: O(rows*max of word length)

S: O(all words total length)

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        StringBuilder sb = new StringBuilder();
        for (String s : sentence) {
            sb.append(s + " ");
        }
        String s = sb.toString();
        int len = s.length();
        
        int cursor = 0;
        for (int i = 0; i < rows; i++) {
            cursor += cols;
            
            if (s.charAt(cursor%len) == ' ') {
                cursor++;
            } else {
                while (cursor >= 0 && s.charAt(cursor%len) != ' ') {
                    cursor--;
                }
                cursor++;
            }
        }
        return cursor/len;
    }
}

more concise version

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        StringBuilder sb = new StringBuilder();
        for (String s : sentence) {
            // if (s.length() > cols) { // notice this case, so if we only make idx min is 0 (idx >= 0)
            //     return 0;
            // }
            sb.append(s + " ");
        }
        String sentenceStr = sb.toString();
        int len = sentenceStr.length();
        
        int idx = 0;
        for (int i = 0; i < rows; i++) {
            idx += cols;
            while (idx >= 0 && sentenceStr.charAt(idx%len) != ' ') { // make idx min is 0, in the last idx/len = 0
                idx--;
            }
            idx++;
        }
        return idx/len;
    }
}

最簡潔的寫法, use String.join(" ", str)

class Solution {
    public int wordsTyping(String[] sentence, int rows, int cols) {
        String s = String.join(" ", sentence) + " ";
        int len = s.length();
        
        int idx = 0;
        for (int i = 0; i < rows; i++) {
            idx += cols;
            while (idx >= 0 && s.charAt(idx%len) != ' ') { // make idx min is 0, in the last idx/len = 0
                idx--;
            }
            idx++;
        }
        return idx/len;
    }
}

這題的這個寫法的想法, 相當 tricky

ex:

Input: sentence = ["a", "bcd", "e"], rows = 3, cols = 6

概念轉換成像是在一個無窮的多個 sentence 組成的長 sentences 上以 row 的長度來做斷句