5
\$\begingroup\$

I got this question in an interview. Given a string of words, print it such as each line has at most limit characters, if a word does not fit on the line, print it on the next line and so on.

This is my implementation:

public static void main(String[] args) {
        String s = "Even aside from the rain and wind it hadn't been a happy practice session. Fred and George, who had been spying on the Slytherin team, had seen for themselves the speed of those new Nimbus Two Thousand and Ones. They reported that the Slytherin team was no more than seven greenish blurs, shooting through the air like missiles.";
        wordWrapper(s, 11);

    }

    public static void wordWrapper(String s, int limit) {
        // Time complexity: O(n) - n size of s
        // Space complexity: O(n) - n number of words in s
        int charCount = 0;
        int i = 0;
        String[] words = s.split(" ");
        while (i < words.length) {
            if (charCount + words[i].length() > limit) {
                System.out.println();
                charCount = 0;
            }
            charCount += words[i].length();
            System.out.print(words[i] + " ");
            i++;
        }
    }

I'm trying to reduce the space complexity, and just use pointers instead of split(), this is what I have so far, I'm thinking of keeping track of the last whitespace and going back to insert a line before that word when the limit is reached, if you run the code the new line is inserted correctly but half of the word would still print before the new line. Please let me know what I'm missing. I also would love to look at better approaches. Thank you!

public static void wordWrapper1(String s, int limit) {
    int i = 0;
    int lastWhitespaceIdx = -1;
    int lineCount = 0;
    if (s.length() == 0) {
        return;
    }
    while (i < s.length()) {
        if (Character.isWhitespace(s.charAt(i))) {
            lastWhitespaceIdx = i;
        }
        if (lineCount + 1 > limit) {
            if (!Character.isWhitespace(s.charAt(i + 1))) {
                i = lastWhitespaceIdx + 1;
                System.out.println();
                lineCount = 0;
                continue;
            } else {
                System.out.println();
                lineCount = 0;
            }
        }
        lineCount += 1;
        System.out.print(s.charAt(i));
        i++;
    }
}
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Hello, since the wordWrapper1 doesn't work, we cannot review or make the correction for you; we can only review the first version (wordWrapper). I suggest that you read the What topics can I ask about here? Code Review aims to help improve working code. If you are trying to figure out why your program crashes or produces a wrong result, ask on Stack Overflow instead. \$\endgroup\$
    – Doi9t
    Oct 11, 2020 at 11:51
  • \$\begingroup\$ I like the first version better. It is much easier to understand. Unless you have measurements that say this code is a hot spot, I would stick with the first. \$\endgroup\$ Oct 11, 2020 at 16:13
  • \$\begingroup\$ @brianbeuning got it, thank you! \$\endgroup\$ Oct 11, 2020 at 21:22
  • \$\begingroup\$ @Doi9t Ok, thank you for pointing that out \$\endgroup\$ Oct 11, 2020 at 21:22

1 Answer 1

3
\$\begingroup\$
        String s = "Even aside from the rain and wind it hadn't been a happy practice session. Fred and George, who had been spying on the Slytherin team, had seen for themselves the speed of those new Nimbus Two Thousand and Ones. They reported that the Slytherin team was no more than seven greenish blurs, shooting through the air like missiles.";

s is not a good variable name. My rule is that you're only allowed to use single-character variable names when dealing with dimensions (yes, that also disallows i/j/k for loops, too).


public static void wordWrapper(String s, int limit) {

The naming is off, this is not a "word wrapper" it's a function that does wrap a string by words, so more like wrap or wrapText.


        // Time complexity: O(n) - n size of s
        // Space complexity: O(n) - n number of words in s

I'm not sure that is correct. I could be very well mistaken here because I rarely need to think about complexity limitations at all, but I think it is closer to "O(n + m)", with "n" being the number of characters (the split), and "m" being the number of words (your loop). Space should be "O(n*2)", with "n" being the number of characters in the string, as you need to keep each character twice in memory, once in the original, and once in the word string.

However, most JVMs are implementing "substrings", which means that the array of codepoints is only held one in memory, and if you do a substring, you will receive a new String with the same array but different start/end index.


        int charCount = 0;
        int i = 0;
        String[] words = s.split(" ");
        while (i < words.length) {
            if (charCount + words[i].length() > limit) {
                System.out.println();
                charCount = 0;
            }
            charCount += words[i].length();
            System.out.print(words[i] + " ");
            i++;
        }

This code could be simplified to a for-each loop:

int currentLineLength = 0;

for (String word : text.split(" ")) {
    if ((currentLineLength + word.length()) > maxCharactersPerLine) {
        System.out.println();
        currentLineLength = 0;
    }
    
    System.out.print(word + " ");
    currentLineLength = currentLineLength + word.length();
}

Note that your implementation, and this revised one, has three problems which should be dealt with at some point:

  1. The spaces are not taken into account for the maximum line length.
  2. It prints an extra space at the end of each line.
  3. How a word should be treated that is longer than the maximum line length.

...and just use pointers instead of split(),...

There is no such thing as "a pointer for strings" in Java. Though, you most likely mean, to iterate over the String and keep track of the index, but "pointer" is a heavily prejudiced word, and I would stay clear of it and instead use "index".


int lastWhitespaceIdx = -1;

Don't shorten names just because you can, it does make the code harder to read in the end of the day.


int lineCount = 0;

The name of this variable is incorrect, it does not count lines, it counts characters on the current line, it should be named accordingly.


while (i < s.length()) {

Not sure why you use a while when a for would be perfect for what you're doing here.


System.out.print(s.charAt(i));

Printing single characters at a time can be quite wasteful, depends on whether the stream supports some sort of buffer or not.


You could use String.indexOf(String) and String.index(String, int) to iterate over the string and simplify your logic. Then use substring to extract the part of the String between the spaces and print that, or print that part character by character.

\$\endgroup\$
1
  • \$\begingroup\$ very helpful, thank you! \$\endgroup\$ Oct 11, 2020 at 21:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.