Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.
Topic describes
This is 68 on LeetCode. Align text left and right, difficulty is difficult.
Tag: “simulation”, “string”
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
- Each word is longer than
Is less than or equal tomaxWidth - Input word array
wordsContains 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 codeExample 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 codeExample 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 codesimulation
String simulation, points can be discussed:
- If there is only one word in the current line, special treatment is left aligned;
- If the current behavior is the last line, the special treatment is left aligned;
- The rest is the general case. Calculate the total length of words in the current line, the total length of Spaces in the current line, and the unit space length rounded down respectively, and then splice them in sequence. When Spaces are not evenly divided, add one more space to the left of each space until the remaining space can be evenly divided by the following Spaces.
Code:
class Solution {
public List<String> fullJustify(String[] words, int maxWidth) {
List<String> ans = new ArrayList<>();
int n = words.length;
List<String> list = new ArrayList<>();
for (int i = 0; i < n; ) {
// list loads all words for the current line
list.clear();
list.add(words[i]);
int cur = words[i++].length();
while (i < n && cur + 1 + words[i].length() <= maxWidth) {
cur += 1 + words[i].length();
list.add(words[i++]);
}
// The last line of the current behavior, with a special left alignment
if (i == n) {
StringBuilder sb = new StringBuilder(list.get(0));
for (int k = 1; k < list.size(); k++) {
sb.append("").append(list.get(k));
}
while (sb.length() < maxWidth) sb.append("");
ans.add(sb.toString());
break;
}
// If there is only one Word in the current line, the special treatment is left aligned
int cnt = list.size();
if (cnt == 1) {
String str = list.get(0);
while(str.length() ! = maxWidth) str +="";
ans.add(str);
continue;
}
/** ** wordWidth: total length of words in the current line; * spaceWidth: total length of current line space; * spaceItem: the rounded unit space length */
int wordWidth = cur - (cnt - 1);
int spaceWidth = maxWidth - wordWidth;
int spaceItemWidth = spaceWidth / (cnt - 1);
String spaceItem = "";
for (int k = 0; k < spaceItemWidth; k++) spaceItem += "";
StringBuilder sb = new StringBuilder();
for (int k = 0, sum = 0; k < cnt; k++) {
String item = list.get(k);
sb.append(item);
if (k == cnt - 1) break;
sb.append(spaceItem);
sum += spaceItemWidth;
// The number of Spaces left (the number of Spaces that can be filled)
int remain = cnt - k - 1 - 1;
// Number of remaining Spaces * minimum space length + current space length < total word length, add one more space to the current space
if (remain * spaceItemWidth + sum < spaceWidth) {
sb.append("");
sum++;
}
}
ans.add(sb.toString());
}
returnans; }}Copy the code- Time complexity: A linear scan is performed for WordsWordswords. In the worst case, each word [I]words[I] Words [I] occupies a single line. In this case, the length of all strings is N ∗maxWidthn * maxWidthn∗maxWidth. O(n∗maxWidth)O(n * maxWidth)O(n∗maxWidth)
- Spatial complexity: in the worst case, each word [I]words[I]words[I] occupies a single line, and the complexity is O(n∗maxWidth)O(n * maxWidth)O(n∗maxWidth)
The last
This is the 68th article in our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions in LeetCode as of the start date, some of which have locks. We will finish all the questions without locks first.
In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.
In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .
In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.