leetcode Text Justification

leetcode Text Justification

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.

题目地址：leetcode Text Justification

题意：给定n个单词，要求将这n个单词按照如下规则打印出来。

1. 每一行长度为L。
2. 单词与单词之间用空格隔开，如果总长度不够L，则补充额外的空格。单词与单纯之间空格数应尽可能相等。
3. 最后一行单词与单词之间不需要补充额外的空格，但是长度也要L

思路：按照题目要求来呗。。。注意细节。

C++

class Solution {
 public:
	 vector<string> fullJustify(vector<string> &words, int L) {
		 vector<string> ans;
		 int n = words.size();	 
		 if (n == 0) return ans;
		 for (int i = 0; i < n;){
			 int cur = i,curL=0;
			 while (cur < n){
				 if (curL + words[cur].length() + cur - i > L) break;
				 curL += words[cur].length();
				 cur++;
			 }
			 int tail = cur;			
			 string line;
			 //last Line
			 if (tail == n){
				 for (int cur = i; cur < tail; cur++){
					 line = line + words[cur];
					 if (cur != tail - 1){
						 curL++;
						 line = line + ' ';
					 }
				 }
				 addSpace(line, L - curL);
			 }
			 else{
				 int totBlank = L - curL;
				 if (tail - i - 1 != 0)
				 {
					 int avg = totBlank / (tail - i - 1);
					 int remain = totBlank % (tail - i - 1);
					 for (int cur = i; cur < tail - 1; cur++){
						 line = line + words[cur];
						 if (remain > 0)
							 addSpace(line, avg + 1);
						 else
							 addSpace(line, avg);
						 remain--;
					 }
					 line = line + words[tail - 1];
				 }
				 else{
					 line = line + words[tail - 1];
					 addSpace(line, totBlank);
				 }			 
			 }
			 ans.push_back(line);
			 i = tail;
		 }
		 return ans;
	 }

	 void addSpace(string & line, int num){
		 while (num--)  line = line + ' ';	 
	 }
 };

 

Python

class Solution:
    # @param words, a list of strings
    # @param L, an integer
    # @return a list of strings
    def fullJustify(self, words, L):
        ans , n ,i =[] , len(words) , 0
        if not n : return ans
        while i < n:
            cur , curL = i , 0
            while cur < n:
                if curL + len(words[cur]) + cur - i > L : break
                curL , cur =  curL + len(words[cur]) , cur + 1
            tail ,line = cur , ''
            if tail == n:
                for cur in range(i,tail):
                    line = line + words[cur]
                    if cur != tail -1 :
                        curL , line = curL+1 , line + ' '
                line = line + ' '*(L-curL)
            else :
                totBlank = L -curL
                if tail - i - 1 != 0:
                    avg ,remain = totBlank / (tail - i - 1) ,totBlank % (tail - i - 1)
                    
                    for cur in range(i,tail-1):
                        line = line + words[cur]
                        if remain > 0:
                            line = line + ' '*(avg+1)
                        else:
                            line = line + ' ' * avg
                        remain-=1
                     
                    line = line + words[tail - 1];
                 
                else:
                    line = line + words[tail - 1]
                    line = line + ' '*(totBlank)
                            
            ans.append(line)             
            i=tail
        return ans