package buildingblock.sorting.merge.lc014_longestcommonprefix;

/**
 * Write a function to find the longest common prefix string amongst an array of strings.
 */
public class Solution {

    // Inspired by soulmachine: compare strs[0] with others
    // Fairly faster than mine...
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        for (int i = 0; i < strs[0].length(); i++) {
            for (int j = 0; j < strs.length; j++) {
                if (strs[j].length() <= i || strs[0].charAt(i) != strs[j].charAt(i)) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

    // My 2nd: O(N^2) time
    public String longestCommonPrefix_ugly(String[] strs) {
        if (strs.length == 0) {
            return "";
        }

        int length = 0;
        while (strs[0].length() > length) { // Happens to put this check here!
            for (int i = 1; i < strs.length; i++) {
                if (strs[i].length() <= length
                        || strs[i - 1].charAt(length) != strs[i].charAt(length)) {
                    return strs[0].substring(0, length);
                }
            }
            length++;
        }
        return strs[0];
    }

    // My 1st: as ugly as my 2nd...
    public String longestCommonPrefix1(String[] strs) {
        if (strs.length == 0) {
            return "";
        }

        int i = 0;
        while (true) {
            if (strs[0].length() - 1 < i) { // error: return i > len-1
                return strs[0].substring(0, i);
            }

            for (int j = 1; j < strs.length; j++) {
                if ((strs[j].length() - 1 < i) || (strs[j-1].charAt(i) != strs[j].charAt(i))) {
                    return strs[j].substring(0, i);
                }
            }
            i++;
        }
    }

}

@@ -180,16 +180,589 @@
 tion %7B%0A%0A
+    public static void main(String%5B%5D args) %7B%0A        Solution sol = new Solution();%0A        System.out.println(sol.longestCommonPrefix(new String%5B%5D%7B%22abc%22, %22ad%22, %22ab%22%7D));%0A    %7D%0A%0A    // O(NK) time.%0A    public String longestCommonPrefix(String%5B%5D strs) %7B%0A        if (strs == null %7C%7C strs.length == 0) return %22%22;%0A        String pre = strs%5B0%5D;%0A        for (int i = 1; i %3C strs.length; i++) %7B%0A            while (!strs%5Bi%5D.startsWith(pre)) // back up tmp LCP if str%5Bi%5D not start with it%0A                pre = pre.substring(0, pre.length() - 1);%0A        %7D%0A        return pre;%0A    %7D%0A%0A
     // I
@@ -876,32 +876,33 @@
 gestCommonPrefix
+3
 (String%5B%5D strs) 

longest common prefix