Description

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

Submissions

Horizontal Scan

One way is to set the prefix to the first string in the array and iteratively shrink it.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) {
            return "";
        }
        
        String prefix = new String(strs[0]);
        for(String str : strs) {
            int i = 0;
            for(; i < str.length() && i < prefix.length(); i++) {
                if(str.charAt(i) != prefix.charAt(i)) {    
                    break;
                }
            }
            prefix = prefix.substring(0, i);
        }
        
        return prefix;
    }
}

class Solution {
public String longestCommonPrefix(String[] strs) {
if(strs.length == 0) {
return “”;
}

    String prefix = new String(strs[0]);
    for(String str : strs) {
        int i = 0;
        for(; i < str.length() && i < prefix.length(); i++) {
            if(str.charAt(i) != prefix.charAt(i)) {    
                break;
            }
        }
        prefix = prefix.substring(0, i);
    }

    return prefix;
}

Vertical Scan

The time complexity depends on the time of scans, obviously, the vertical scan will reduce the time since it can scan the least of the letters.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) return "";
        for(int i = 0; ; i++) {
            if(strs[0].length() == i) {
                return strs[0];
            }
            char c = strs[0].charAt(i);
            for(String str : strs) {
                if(str.length() == i) {
                    return str;
                }
                
                if(str.charAt(i) != c) {
                    return str.substring(0, i);
                }
            }
        }
    }
}