leetcode/src/Text_Justification.cpp at master · zyx4843/leetcode · GitHub

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
124
125
126
127
// Source : https://oj.leetcode.com/problems/text-justification/
// Author : zheng yi xiong
// Date   : 2015-01-31

/**********************************************************************************
*
* Given an array of words and a length L, format the text such that each line has exactly L 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 L 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.

* For example,
* words: ["This", "is", "an", "example", "of", "text", "justification."]
* L: 16.

* Return the formatted lines as:
* [
*  "This    is    an",
*  "example  of text",
*  "justification.  "
* ]
* Note: Each word is guaranteed not to exceed L in length.

* click to show corner cases.

* Corner Cases:
*  A line other than the last line might contain only one word. What should you do in this case?
*  In this case, that line should be left-justified.
*
**********************************************************************************/
#include "stdafx.h"
#include <iostream>
#include <vector>
#include <string>

using namespace std;

class Solution {
public:
	vector<string> fullJustify(vector<string> &words, int L) {
		vector<string> retVec;
		if (words.empty())
		{
			return retVec;
		}

		int retNo = 0, wordStart = 0, wordEnd = 1, stringLen = words[0].length() + 1;
		int extraNum = 0, eachExtra = 0, moreExtra = 0;
		int i = 1;
		for (; i < words.size(); ++i)
		{
			if (stringLen + words[i].length() > L)
			{
				extraNum = L - stringLen + 1;
				if (1 < wordEnd - wordStart)
				{
					eachExtra = extraNum / (wordEnd - wordStart - 1) + 1;
					moreExtra = extraNum % (wordEnd - wordStart - 1);
					retVec.push_back(words[wordStart++]);
					for (int j = 0; j < moreExtra; ++j)
					{
						for (int k = 0; k < eachExtra + 1; ++k)
						{
							retVec[retNo].push_back(' ');
						}
						retVec[retNo] += words[wordStart++];
					}

					for (; wordStart < wordEnd; ++wordStart)
					{
						for (int k = 0; k < eachExtra; ++k)
						{
							retVec[retNo].push_back(' ');
						}
						retVec[retNo] += words[wordStart];
					}
				}
				else
				{
					retVec.push_back(words[wordStart]);
					for (int j = 0; j < extraNum; ++j)
					{
						retVec[retNo].push_back(' ');
					}
				}
				++retNo;
				wordStart = i;
				stringLen = 0;
			}
			stringLen += words[i].length() + 1;
			wordEnd = i + 1;
		}

		extraNum = L - stringLen + 1;
		retVec.push_back(words[wordStart++]);
		for (; wordStart < wordEnd; ++wordStart)
		{
			retVec[retNo].push_back(' ');
			retVec[retNo] += words[wordStart];
		}

		for (int j = 0; j < extraNum; ++j)
		{
			retVec[retNo].push_back(' ');
		}

		return retVec;
	}
};

int _tmain(int argc, _TCHAR* argv[])
{
	vector<string> words;
	words.push_back("This");
	words.push_back("is");
	words.push_back("an");
	words.push_back("example");
	words.push_back("of");
	words.push_back("text");
	words.push_back("justification.");
	Solution so;
	vector<string> vecRet = so.fullJustify(words, 16);
	return 0;
}