FilesExpand file tree

 master

/

068_TextJustification68.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

123 lines (118 loc) · 3.86 KB

 master

/

068_TextJustification68.java

Copy path

Top

File metadata and controls

• Code
• Blame

123 lines (118 loc) · 3.86 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

/**

* Given an array of words and a width maxWidth, format the text such that each

* line has exactly maxWidth characters and is fully (left and right) justified.

*

* You should pack your words in a greedy approach; that is, pack as many words

* as you can in each line. Pad extra spaces ' ' when necessary so that each

* line has exactly maxWidth characters.

*

* Extra spaces between words should be distributed as evenly as possible. If

* the number of spaces on a line do not divide evenly between words, the empty

* slots on the left will be assigned more spaces than the slots on the right.

*

* For the last line of text, it should be left justified and no extra space is

* inserted between words.

*

* Note:

* A word is defined as a character sequence consisting of non-space characters only.

* Each word's length is guaranteed to be greater than 0 and not exceed maxWidth.

* The input array words contains at least one word.

*

* Example 1:

* Input:

* words = ["This", "is", "an", "example", "of", "text", "justification."]

* maxWidth = 16

* Output:

* [

* "This is an",

* "example of text",

* "justification. "

* ]

*

* Example 2:

* Input:

* words = ["What","must","be","acknowledgment","shall","be"]

* maxWidth = 16

* Output:

* [

* "What must be",

* "acknowledgment ",

* "shall be "

* ]

* Explanation: Note that the last line is "shall be " instead of "shall be",

* because the last line must be left-justified instead of fully-justified.

* Note that the second line is also left-justified becase it contains only one word.

*

* Example 3:

* Input:

* words = ["Science","is","what","we","understand","well","enough","to",

* "explain","to","a","computer.","Art","is","everything","else","we","do"]

* maxWidth = 20

* Output:

* [

* "Science is what we",

* "understand well",

* "enough to explain to",

* "a computer. Art is",

* "everything else we",

* "do "

* ]

*/

import java.util.*;

public class TextJustification68 {

public List<String> fullJustify(String[] words, int maxWidth) {

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

int i = 0;

int N = words.length;

while (i < N) {

int spaceLeft = maxWidth;

int wordsLen = 0;

List<String> line = new ArrayList<>();

while (i < N) {

if (words[i].length() > spaceLeft) break;

line.add(words[i]);

wordsLen += words[i].length();

spaceLeft -= words[i].length() + 1;

i++;

}

StringBuilder sb = new StringBuilder();

if (i == N || line.size() == 1) {

res.add(leftJustify(line, maxWidth));

} else {

res.add(middleJustify(line, maxWidth, wordsLen));

}

}

return res;

}

private String leftJustify(List<String> line, int maxWidth) {

StringBuilder sb = new StringBuilder();

for (String w: line) {

sb.append(w);

if (sb.length() < maxWidth) sb.append(' ');

}

while (sb.length() < maxWidth) {

sb.append(' ');

}

return sb.toString();

}

private String middleJustify(List<String> line, int maxWidth, int wordsLen) {

StringBuilder sb = new StringBuilder();

int n = line.size();

int spaces = maxWidth - wordsLen;

int interval = spaces / (n-1);

int rest = spaces - interval * (n-1);

for (int k=0; k<n; k++) {

sb.append(line.get(k));

int p = interval;

while (p > 0 && sb.length() < maxWidth) {

sb.append(' ');

p--;

}

if (rest > 0 && sb.length() < maxWidth) {

sb.append(' ');

rest--;

}

}

return sb.toString();

}

}