[LC 418]. Sentence Screen Fitting

首先用最intuitive的方法做了一下,就是一个词一个词看是否能fit当前row,然后记录写下了几个sentence。得到了正确答案,但是time limit exceed.

然后看了论坛,明白了思路:不是一个词一个词往row里面装,而是假设string是无限循环下去的,记录所有row走完会move到哪里。最后start指针的值相当于一共在screen上有多少字符具体说包含以下步骤:
1. 先把sentence连起来,然后摊平。例如:[“abc”, “de”, “f”],连成sentence是”abc de f “,设想这个sentence无限循环,就是”abc de f abc de f abc de f abc…”
2. 用一个pointer记录每一行的start,每多一个row,把pointer往后移动cols个。
3. 移动pointer时两种情况需要处理一下:(1) 一行的开头刚好是space,start指针直接+1,即remove一个space,(2)一行的开头刚好是一个word的中间,start需要退回到该word的开头,即在上一行增加一些space。

    public int wordsTyping(String[] sentence, int rows, int cols) {
        if (sentence == null || sentence.length == 0 || rows == 0 || cols == 0) return 0;
        String s = String.join(" ", sentence) + " ";
        int len = s.length();
        int start = 0;
        for (int i = 0; i < rows; i++) {
            start += cols;
            if (s.charAt(start % len) == ' ') {
                start++;
            } else {
                while (start > 0 && s.charAt((start - 1) % len) != ' ') {
                    start--;
                }
            }
        }
        
        return start / len;
    }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s