Java solution with O(nk) time and minimal memory footprint


  • 0
    J

    Since the longest common prefix must appear in all items, I choose strs[0] as the container. Then I use only one pointer, "length", to track the size of the common prefix.

    I used only one subString() to extract the prefix at the end. The computational & memory overhead is minimized.

        if (strs.length == 0) return "";
        int length = strs[0].length();
        for (int i = 1; i < strs.length; i++) {
            length = Math.min(length, strs[i].length());
            for (int j = 0; j < length; j++) {
                if (strs[0].charAt(j) != strs[i].charAt(j)) {
                    length = j;
                    break;
                }
            }
        }
        return (length == 0) ? "" : strs[0].substring(0, length);

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.