add 418

fishercoder1534 · fishercoder1534 · commit 249bf6bc2f7d · 2017-06-11T10:08:26.000-07:00
diff --git a/README.md b/README.md
@@ -160,6 +160,7 @@ Your ideas/fixes/algorithms are more than welcome!
 |421|[Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_421.java)| O(n) | O(1) | Medium | Bit Manipulation, Trie
 |420|[Strong Password Checker](https://leetcode.com/problems/strong-password-checker/)|[Solution](../master/src/main/java/com/fishercoder/solutions/StrongPasswordChecker.java)| ? | ? | Hard| 
 |419|[Battleships in a Board](https://leetcode.com/problems/battleships-in-a-board/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_419.java) | O(m*n) |O(1) | Medium| DFS
+|418|[Sentence Screen Fitting](https://leetcode.com/problems/sentence-screen-fitting/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_418.java) | O(n) |O(1) | Medium| 
 |417|[Pacific Atlantic Water Flow](https://leetcode.com/problems/pacific-atlantic-water-flow/)|[Solution](../master/src/main/java/com/fishercoder/solutions/PacificAtlanticWaterFlow.java) | O(m*n*Max(m,n)) |O(m*n) | Medium| DFS
 |416|[Partition Equal Subset Sum](https://leetcode.com/problems/partition-equal-subset-sum/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_416.java)| O(m*n)|O(m*n) | Medium | DP
 |415|[Add Strings](https://leetcode.com/problems/add-strings/)|[Solution](../master/src/main/java/com/fishercoder/solutions/_415.java)| O(n)|O(1) | Easy|
diff --git a/src/main/java/com/fishercoder/solutions/_418.java b/src/main/java/com/fishercoder/solutions/_418.java
@@ -0,0 +1,89 @@
+package com.fishercoder.solutions;
+
+/**
+ * 418. Sentence Screen Fitting
+ *
+ * Given a rows x cols screen and a sentence represented by a list of non-empty words, find how many times the given sentence can be fitted on the screen.
+
+ Note:
+
+ A word cannot be split into two lines.
+ The order of words in the sentence must remain unchanged.
+ Two consecutive words in a line must be separated by a single space.
+ Total words in the sentence won't exceed 100.
+ Length of each word is greater than 0 and won't exceed 10.
+ 1 ≤ rows, cols ≤ 20,000.
+
+ Example 1:
+
+ Input:
+ rows = 2, cols = 8, sentence = ["hello", "world"]
+
+ Output:
+ 1
+
+ Explanation:
+ hello---
+ world---
+
+ The character '-' signifies an empty space on the screen.
+
+ Example 2:
+
+ Input:
+ rows = 3, cols = 6, sentence = ["a", "bcd", "e"]
+
+ Output:
+ 2
+
+ Explanation:
+ a-bcd-
+ e-a---
+ bcd-e-
+
+ The character '-' signifies an empty space on the screen.
+
+ Example 3:
+
+ Input:
+ rows = 4, cols = 5, sentence = ["I", "had", "apple", "pie"]
+
+ Output:
+ 1
+
+ Explanation:
+ I-had
+ apple
+ pie-I
+ had--
+
+ The character '-' signifies an empty space on the screen.
+
+ */
+public class _418 {
+
+    /**credit: https://discuss.leetcode.com/topic/62455/21ms-18-lines-java-solution
+     *
+     1. String s = String.join(" ", sentence) + " " ;. This line gives us a formatted sentence to be put to our screen.
+     2. start is the counter for how many valid characters from s have been put to our screen.
+     3. if (s.charAt(start % l) == ' ') is the situation that we don't need an extra space for current row. The current row could be successfully fitted. So that we need to increase our counter by using start++.
+     4. The else is the situation, which the next word can't fit to current row. So that we need to remove extra characters from next word.
+     5. start / s.length() is (# of valid characters) / our formatted sentence.
+     */
+    public int wordsTyping(String[] sentence, int rows, int cols) {
+        String s = String.join(" ", sentence) + " ";
+        int start = 0, l = s.length();
+        for (int i = 0; i < rows; i++) {
+            start += cols;
+            if (s.charAt(start % l) == ' ') {
+                start++;
+            } else {
+                while (start > 0 && s.charAt((start-1) % l) != ' ') {
+                    start--;
+                }
+            }
+        }
+        return start / s.length();
+    }
+
+}
diff --git a/src/test/java/com/fishercoder/_418Test.java b/src/test/java/com/fishercoder/_418Test.java
@@ -0,0 +1,56 @@
+package com.fishercoder;
+
+import com.fishercoder.solutions._418;
+import org.junit.BeforeClass;
+import org.junit.Test;
+
+import static org.junit.Assert.assertEquals;
+
+/**
+ * Created by stevesun on 6/11/17.
+ */
+public class _418Test {
+    private static _418 test;
+    private static String[] sentence;
+
+    @BeforeClass
+    public static void setup(){
+        test = new _418();
+    }
+
+    @Test
+    public void test1(){
+        sentence = new String[]{"hello", "world"};
+        assertEquals(1, test.wordsTyping(sentence, 2, 8));
+    }
+
+    @Test
+    public void test2(){
+        sentence = new String[]{"a", "bcd", "e"};
+        assertEquals(2, test.wordsTyping(sentence, 3, 6));
+    }
+
+    @Test
+    public void test3(){
+        sentence = new String[]{"I", "had", "apple", "pie"};
+        assertEquals(1, test.wordsTyping(sentence, 4, 5));
+    }
+
+    @Test
+    public void test4(){
+        sentence = new String[]{"f", "p", "a"};
+        assertEquals(10, test.wordsTyping(sentence, 8, 7));
+    }
+
+    @Test
+    public void test5(){
+        sentence = new String[]{"hello","leetcode"};
+        assertEquals(1, test.wordsTyping(sentence, 1, 20));
+    }
+
+    @Test
+    public void test6(){
+        sentence = new String[]{"h"};
+        assertEquals(4, test.wordsTyping(sentence, 2, 3));
+    }
+}
