Leetcode -68- Align text left and right

[Blog link]

The path to learning at 🐔

The nuggets home page

[答 案]

Topic link

[making address]

Making the address

[B].

Given an array of words and a maxWidth of length, retype the words so that each line has exactly maxWidth characters and is aligned right and left.

You should use a “greedy algorithm” to place a given word; That is, put as many words in each line as possible. Padding with Spaces “if necessary, so that each line has exactly maxWidth characters.

The number of Spaces between words should be distributed as evenly as possible. If the space between words on a line is not evenly distributed, more space is placed on the left than on the right.

The last line of text should be left aligned and no extra Spaces inserted between words.

Description:

A word is a sequence of characters that is not a space character. The length of each word is greater than 0 and less than or equal to maxWidth. The input word array words contains at least one word. Example:

Input: words = ["This", "is", "an", "example", "of", "text", "justification."] maxWidth = 16 [ "This is an", "example of text", "justification. " ]Copy the code

Example 2:

Input: words = ["What","must","be"," Acknowledgment ","shall","be"] maxWidth = 16 output: ["What must be", "Acknowledgment ", "shall be"] Explanation: Note that the format of the last line should be" shall be" instead of "shall be", because the last line should be aligned left, not left. The second line is also left justified because it contains only one word.Copy the code

Example 3:

Input: words = ["Science","is","what","we","understand","well","enough","to","explain", "To", "a", "computer.", "Art", "is", "everything", "else" and "we", "do"] maxWidth = 20 output: [ "Science is what we", "understand well", "enough to explain to", "a computer. Art is", "everything else we", "do " ]Copy the code

Idea 1: String simulation

• There should be at least one space between each word
• So with this condition the idea is pretty simple
• There are three cases:
  • Just one word: left-justified
  • Multiple words – not the last line:
    • The number of Spaces between each word is the same
    • The number of Spaces between each word varies: add one space from left to right until the maximum length is met
  • Multiple words – Last line: left justified, place a space in the middle of each word, then complete all Spaces

class Solution {

    List<String> res = new ArrayList<>();
    int max;

    public List<String> fullJustify(String[] words, int maxWidth) {
        int n = words.length;
        max = maxWidth;
        if (n == 1) {
            StringBuilder sb = new StringBuilder(words[0]);
            while (sb.length()<maxWidth){
                sb.append("");
            }
            res.add(sb.toString());
            return res;
        }
        int i = 0;
        while (i < n) {
            int tempL = 0, start = i;
            // The greedy method makes sure that the words are placed on a line with at least one space between each word
            while (i < n && tempL + words[i].length() <= maxWidth) {
                tempL += words[i].length();
                if (tempL < maxWidth) {
                    tempL++;
                    i++;
                } else {
                    i++;
                    break;
                }
            }
            processString(words, start, i);
        }
        return res;
    }

    public void processString(String[] words, int start, int end) {
        // Multiple words
        int sum = 0;
        for (int i = start; i < end; i++) {
            sum += words[i].length();
        }
        int space = max - sum;
        // The last line is handled separately
        if (end == words.length) {
            StringBuilder sb = new StringBuilder();
            for (int i = start; i < words.length; i++) {
                sb.append(words[i]);
                if(i ! = words.length -1) {
                    sb.append(""); }}while (sb.length() < max) {
                sb.append("");
            }
            res.add(sb.toString());
            return;
        }
        // There is only one word, put it on the left, and complete the blanks
        if (end - start - 1= =0) {
            StringBuilder sb = new StringBuilder(words[start]);
            while (sb.length() < max) {
                sb.append("");
            }
            res.add(sb.toString());
            return;
        }
        // The number of Spaces is evenly split, with the same number of Spaces in the middle of each word
        if (space % (end - start - 1) = =0) {
            // Find the space between each word
            int v = space / (end - start - 1);
            StringBuilder sp = new StringBuilder();
            for (int i = 0; i < v; i++) {
                sp.append("");
            }
            StringBuilder sb = new StringBuilder();
            for (int i = start; i < end; i++) {
                sb.append(words[i]);
                // No space after the last word
                if(i ! = end -1) {
                    sb.append(sp);
                }
            }
            res.add(sb.toString());
        }
        // The space between words is not evenly split
        else {
            int v = space / (end - start - 1);
            // Add space between the first two words
            int cv = space % (end - start - 1);
            StringBuilder sp = new StringBuilder();
            for (int i = 0; i < v; i++) {
                sp.append("");
            }
            StringBuilder sb = new StringBuilder();
            for (int i = start; i < end; i++) {
                sb.append(words[i]);
                if (i - start < cv ) {
                    sb.append("");
                }
                if(i ! = end -1) { sb.append(sp); } } res.add(sb.toString()); }}}Copy the code

• Time complexity O(n * maxWidth)
• Space complexity O(n)