14. Longest Common Prefix

time: O(s), all the chars

space: O(1)

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // [abc, cds, ab] => ""
        // [abc, ab, a] => "a"
        // [aaa, bbb, cc] = > ""
        // fiist is to compare each char in string array one by one, it will be n^2
        
        // another one is base on first String, compare others and narrow the String range,
        if (strs == null || strs.length == 0) return "";
        
        String pre = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (!strs[i].startsWith(pre)) {
                pre = pre.substring(0, pre.length() - 1);
            }
        }
        return pre;
     }
}

like binary search idea, separate to two parts

time: O(slogn), s: all the chars

space: O(1)

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        
        int minLength = Integer.MAX_VALUE;
        for (String str : strs) {
            minLength = Math.min(minLength, str.length());
        }
        int low = 0; // it's should be 1
        int high = minLength;
        while (low <= high) {
            int mid = (low + high) >> 1;
            if (isCommon(strs, mid)) { // isCommon, so it can increase the common length
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return strs[0].substring(0, (low+high)/2);
    }
    private boolean isCommon(String[] strs, int index) {
        String pre = strs[0].substring(0, index);
        for (int i = 1; i < strs.length; i++) {
            if (!strs[i].startsWith(pre)) {
                return false;
            }       
        }
        return true;
    }
}