text justification

fishercoder1534 · fishercoder1534 · commit aa750d0f9f4d · 2016-10-09T21:36:06.000-07:00
diff --git a/HARD/src/hard/TextJustification.java b/HARD/src/hard/TextJustification.java
@@ -0,0 +1,68 @@
+package hard;
+import java.util.*;
+/**
+ * Created by fishercoder1534 on 10/9/16.
+ */
+public class TextJustification {
+
+    public static List<String> fullJustify(String[] words, int L) {
+        ArrayList<String> result = new ArrayList();
+        if(words == null || words.length == 0)
+            return result;
+        int count = 0;
+        int last = 0;
+        for(int i = 0; i < words.length; i++){
+            if(count + words[i].length() + (i-last) > L){
+                int spaceNum = 0 ;
+                int extraNum = 0;
+                if(i - last - 1 > 0){
+                    spaceNum = (L - count)/(i - last - 1);
+                    extraNum = (L - count)%(i - last - 1);
+                }
+                StringBuilder sb = new StringBuilder();
+                for(int j = last; j < i; j++){
+                    sb.append(words[j]);
+                    if(j < i-1){
+                        for(int k = 0; k < spaceNum; k++){
+                            sb.append(" ");
+                        }
+                        if(extraNum > 0){
+                            sb.append(" ");
+                        }
+                        extraNum--;
+                    }
+                }
+                for(int j = sb.length(); j < L; j++){
+                    sb.append(" ");
+                }
+                result.add(sb.toString());
+                count = 0;
+                last = i;
+            }
+            count += words[i].length();
+        }
+        StringBuilder sb = new StringBuilder();
+        for(int i = last; i < words.length; i++){
+            sb.append(words[i]);
+            if(sb.length() < L){
+                sb.append(" ");
+            }
+        }
+        for(int i = sb.length(); i < L; i++){
+            sb.append(" ");
+        }
+        result.add(sb.toString());
+        return result;
+    }
+
+    public static void main(String...args){
+//        String[] words = new String[]{"This", "is", "an", "example", "of", "text", "justification."};
+        String[] words = new String[]{"This", "is", "a", "good", "test!", "\n", "What", "do", "you", "\n", "think?", "\n", "I"
+                , "think", "so", "too!"};
+        int L = 16;
+        List<String> result = fullJustify(words, L);
+        for(String str : result) {
+            System.out.println(str);
+        }
+    }
+}
diff --git a/README.md b/README.md
@@ -29,6 +29,7 @@
 |78|[Subsets](https://leetcode.com/problems/subsets/)|[Solution](../../blob/master/MEDIUM/src/medium/Subsets.java)|O(n^2) ? |O(1)|Medium|Backtracking
 |76|[Minimum Window Substring](https://leetcode.com/problems/minimum-window-substring/)|[Solution](../../blob/master/HARD/src/hard/MinimumWindowSubstring.java)|O(n)|O(k)|Hard|Two Pointers
 |75|[Sort Colors](https://leetcode.com/problems/sort-colors/)|[Solution]|O(n)|O(1)|Medium
+|68|[Text Justification](https://leetcode.com/problems/text-justification/)|[Solution](../../blob/master/HARD/src/hard/TextJustification.java)|O(n)|O(1)|HARD|
 |67|[Add Binary](https://leetcode.com/problems/add-binary/)|[Solution](../../blob/master/EASY/src/easy/AddBinary.java)|O(n)|O(1)|Easy|
 |56|[Merge Intervals](https://leetcode.com/problems/merge-intervals/)|[Solution](../../blob/master/HARD/src/hard/MergeIntervals.java)|O(n*logn)|O(1)|Hard|
 |43|[Multiply Strings](https://leetcode.com/problems/multiply-strings/)|[Solution]|||Medium
