LongestCommonPrefix14

fluency03 · fluency03 · commit 6a5058ccb37f · 2017-06-28T14:23:46.000+02:00
diff --git a/README.md b/README.md
@@ -10,7 +10,7 @@
 
 
 
-# Total: 50
+# Total: 51
 
 
 | Question | Solution | Difficulty |
@@ -20,6 +20,7 @@
 | [3. Longest Substring Without Repeating Characters](https://leetcode.com/problems/longest-substring-without-repeating-characters/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/LongestSubstringWithoutRepeatingCharacters3.java) | Medium |
 | [5. Longest Palindromic Substring](https://leetcode.com/problems/longest-palindromic-substring/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/LongestPalindromicSubstring5.java) | Medium |
 | [8. String to Integer (atoi)](https://leetcode.com/problems/string-to-integer-atoi/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/StringToInteger8.java) | Medium |
+| [14. Longest Common Prefix](https://leetcode.com/problems/longest-common-prefix/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/LongestCommonPrefix14.java) | Easy |
 | [15. 3Sum](https://leetcode.com/problems/3sum/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/ThreeSum15.java) | Medium |
 | [16. 3Sum Closest](https://leetcode.com/problems/3sum-closest/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/ThreeSumClosest16.java) | Medium |
 | [20. Valid Parentheses](https://leetcode.com/problems/valid-parentheses/) | [Solution](https://github.com/fluency03/leetcode-java/blob/master/src/ValidParentheses20.java) | Easy |
diff --git a/src/LongestCommonPrefix14.java b/src/LongestCommonPrefix14.java
@@ -0,0 +1,40 @@
+/**
+ * Write a function to find the longest common prefix string amongst an array of strings.
+ */
+
+
+public class LongestCommonPrefix14 {
+    public String longestCommonPrefix(String[] strs) {
+        String lcp = "";
+        int S = strs.length;
+        if (S == 0) return lcp;
+
+        int L = strs[0].length();
+        int idx = 0;
+        for (int i = 1; i < S; i++) {
+            if (strs[i].length() < L) {
+                L = strs[i].length();
+                idx = i;
+            }
+        }
+        if (L == 0) return lcp;
+
+        int p = 1;
+        String possible = strs[idx];
+        while (p <= L) {
+            String sub = possible.substring(0, p);
+            boolean b = true;
+            for (int k = 0; k < S; k++) {
+                if (!strs[k].startsWith(sub)) {
+                    b = false;
+                    break;
+                }
+            }
+            if (!b) break;
+            lcp = sub;
+            p++;
+        }
+
+        return lcp;
+    }
+}
