21ms 18 lines Java solution


  • 139
    K

    Update: See @iambright's post below for optimized code.
    Update: If you want to shorten the code by getting rid of either the while loop or the if-else check, see update below.

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

    Update (4/7/2017): There is a way to get rid of the if-else check (see discussion below). If you would like to shorten the code, see the shorter code below first.

        public int wordsTyping(String[] sentence, int rows, int cols) {
            String s = String.join(" ", sentence) + " ";
            int[] offset = new int[s.length()];
            IntStream.range(1, s.length()).forEach(i -> offset[i] = s.charAt(i) == ' ' ? 1 : offset[i-1]-1);
            return IntStream.range(0, rows).reduce(0, (a, b) -> a + cols + offset[(a+cols) % s.length()]) / s.length();
        }
    

    Explanation:

    Say sentence=["abc", "de", "f], rows=4, and cols=6.
    The screen should look like

    "abc de"
    "f abc "
    "de f  "
    "abc de"
    

    Consider the following repeating sentence string, with positions of the start character of each row on the screen.

    "abc de f abc de f abc de f ..."
     ^      ^     ^    ^      ^
     0      7     13   18     25
    

    Our goal is to find the start position of the row next to the last row on the screen, which is 25 here. Since actually it's the length of everything earlier, we can get the answer by dividing this number by the length of (non-repeated) sentence string. Note that the non-repeated sentence string has a space at the end; it is "abc de f " in this example.

    Here is how we find that position. In each iteration, we need to adjust start based on spaces either added or removed.

    "abc de f abc de f abc de f ..." // start=0
     012345                          // start=start+cols+adjustment=0+6+1=7 (1 space removed in screen string)
            012345                   // start=7+6+0=13
                  012345             // start=13+6-1=18 (1 space added)
                       012345        // start=18+6+1=25 (1 space added)
                              012345
    

    Hope this helps.


  • 64
    F

    Good job! Nice solution.

    Let me explain a little to help others understand this solution well.

    1. String s = String.join(" ", sentence) + " " ;. This line gives us a formatted sentence to be put to our screen.
    2. start is the counter for how many valid characters from s have been put to our screen.
    3. if (s.charAt(start % l) == ' ') is the situation that we don't need an extra space for current row. The current row could be successfully fitted. So that we need to increase our counter by using start++.
    4. The else is the situation, which the next word can't fit to current row. So that we need to remove extra characters from next word.
    5. start / s.length() is (# of valid characters) / our formatted sentence.

  • 0
    Y

    Nice solution. Thx!


  • 0
    I

    @kylejao For last char in the row, you can test "s.charAt((start + l - 1) % l) != ' '" instead of start > 0 && ...


  • 60
    I

    Optimized to 12ms. O(m + n), m: length of sentence by char, n: rows.

    public int wordsTyping(String[] sentence, int rows, int cols) {
        String s = String.join(" ", sentence) + " ";
        int len = s.length(), count = 0;
        int[] map = new int[len];
        for (int i = 1; i < len; ++i) {
            map[i] = s.charAt(i) == ' ' ? 1 : map[i-1] - 1;
        }
        for (int i = 0; i < rows; ++i) {
            count += cols;
            count += map[count % len];
        }
        return count / len;
    }
    

  • 0
    K

    @iambright That's nice. Thanks.


  • 5
    H

    Thanks. Here is a python implementation.

    class Solution(object):
        def wordsTyping(self, sentence, rows, cols):
            """
            :type sentence: List[str]
            :type rows: int
            :type cols: int
            :rtype: int
            """
            s = " ".join(sentence) + " "
            start, n = 0, len(s)
            for i in range(0, rows):
                start += cols
                if s[start % n] == " ":
                    start += 1
                else:
                    while start > 0 and s[(start-1) % n] != " ":
                        start -= 1
            return start / n
    

  • 0

    @iambright said in 21ms 18 lines Java solution:

    Why we should do "-1" in start + l - 1, what does it mean please?


  • 9

    Great solution, simple and clear.
    Here's a C++ version for reference:

    int wordsTyping(vector<string>& sentence, int rows, int cols) {
            string s = "";                                          // s is the formatted sentence to be put to our screen
            for (string word : sentence) { s += " " + word; }
            
            int start = 1;                                          // skip the very first space char ' '
            for (int r = 0; r < rows; r++, start++) {               // advance start by one so s[start & s.length()] != ' '
                start += cols;                                      // full fill current collumn, so start advance by cols
                while (s[start % s.length()] != ' ') { start--; }   // make sure s[start & s.length()] == ' '
            }
            
            return --start / s.length();                            // we began with start == 1, so (start-1) is the valid length
    }
    

  • 0
    S

    This solution is very impressive!


  • 0
    H

    Brilliant solution! I'm trying to analyze the time complexity. I think first we need to traverse each row, and in the while loop in each row, it can execute MaxWordLength times. So is the time complexity O(Row * MaxWordLen)? Correct me if I'm wrong :)


  • 0
    K

    @hu19 said in 21ms 18 lines Java solution:

    Brilliant solution! I'm trying to analyze the time complexity. I think first we need to traverse each row, and in the while loop in each row, it can execute MaxWordLength times. So is the time complexity O(Row * MaxWordLen)? Correct me if I'm wrong :)

    You are right. But with iambright's idea, it will be linear.


  • 0
    X

    Amazing Solution


  • 3

    @hu19 Let R=rows, Lw = MaxWordLen, Ls = SentenceLen, then yes, @soamaaazing 's solution indeed has O(R*Lw) time.
    Note that all "while (s[start % s.length()] != ' ') start--;" does is simply to step back to the previous " "in the sentence and once location startis fixed, the result is the same. So the difference between @soamaaazing and @iambright 's solutions is that @iambright pre-calculate (or "cached") the number of step-backs for every location in sentence and stores them in map (which I think a more descriptive name would be better), so we don't need to re-compute again during the loop over rows.
    The intuitive assumption here is that rows is typically much larger than Lw, so it makes sense for @iambright 's solution to sacrifice O(Ls)space in exchange of a factor of Lw in speed-up. For the constraint of this problem, rows <= 20000, Lw <= 10, Ls <= 10*100 + (100-1) = 1099, so I guess not much difference. If the sentence is really long and contains only very short words, then @soamaaazing 's solution is better at saving space.


  • 0

    Great solution and great observation by not breaking up the sentence in words! If you break into words, you will get TLE (like I did initially...). The trick here is that the problem is defined in a very uniform way (size is only proportional to length) and the sentence is repeatedly printed, so there is absolutely no reason to break up into the same set of words again and again!

    I've seen a different variation of this problem, which involves font size and different letters could have different wdith and height for a given font size. And asks the largest font size to fit the sentence once on the screen. The idea is to use binary search to find the largest font size, but for each font size, the sentence has to be broken into words to figure out the total height.


  • 0
    4

    Hi guys,

    Can someone explain me the case when say sentence=["leet"], rows=1, and cols=4.

    Here, l = 4. According to the solution, we will do start = start + cols i.e. start will become 4. Now, s.charAt(start % l) will not be ' '.So, we will go on decrementing start till start = 0. And now, final solution will be 0. Shouldn't it be 1. Am I missing something?

    Thanks for your time :)


  • 1
    K

    @anujbora said in 21ms 18 lines Java solution:

    Hi guys,

    Can someone explain me the case when say sentence=["leet"], rows=1, and cols=4.

    Here, l = 4. According to the solution, we will do start = start + cols i.e. start will become 4. Now, s.charAt(start % l) will not be ' '.So, we will go on decrementing start till start = 0. And now, final solution will be 0. Shouldn't it be 1. Am I missing something?

    Thanks for your time :)

    First, l = 5 as s = "leet " (one trailing space). When start=4, since s[4] is a space, start will be incremented by 1.

    You can try to print out the variables when running with your case.

    Thanks.


  • 1
    H

    Hi guys, I still don't understand why (s.charAt(start % l) == ' ') we have to increment start by 1? I know it's the situation where we don't need extra space for the row, but I mean, if we "don't need that space and the word already fit in the row", shouldn't we decrement start by 1 instead?


  • 2
    K

    @hgdangkhoi said in 21ms 18 lines Java solution:

    Hi guys, I still don't understand why (s.charAt(start % l) == ' ') we have to increment start by 1? I know it's the situation where we don't need extra space for the row, but I mean, if we "don't need that space and the word already fit in the row", shouldn't we decrement start by 1 instead?

    Think about "abc de f". When at the space between "de" and "f", you are looking for the position of the first word in the next row, which is "f", and so you move start forward by 1.


  • 0

    @iaming what is the meaning of array map?


Log in to reply
 

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