Simple JAVA implementation


  • 2

    Thought of this problem as stacking up all of the strings on top of each other (not the data structure just logically) and analyzing first character for each string then second character for each string and so. Each time a character has been validated to each in each string in the array that character is appended stringBuilder (sb) object. This process continues until a character does match the others or a string is smaller than the others. I arbitrarily selected the first string in array of string to compare all others to. It doesn't matter since the prefix must match all Strings in the array.

    The complexity of this algorithm let n be the length of the input array strs let m be the length of the shortest String in the array: Time complexity is O(n * m)

    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) return "";
        if(strs.length == 1) return strs[0];
        StringBuilder sb = new StringBuilder();
        
        for(int i = 0; i < strs[0].length(); i++){
            char c = strs[0].charAt(i);
            for(int j = 1; j < strs.length; j++){
                if(i >= strs[j].length()) return sb.toString();
                if(c != strs[j].charAt(i)) return sb.toString();
            }
            sb.append(c);
        }return sb.toString();
    }

Log in to reply
 

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