LeetCode:Longest Common Prefix

Longest Common Prefix



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

A Java solution by checking the common prefix char-by-char:

Starting from the first char of the first string, and check if all other strings have it in the same position. Loop over each char. 

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int n = strs.length;
        if(n==0) return "";
        int i=0;
        for(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() || strs[j].charAt(i)!=c) return strs[0].substring(0,i);
            }
        }
        return strs[0].substring(0,i);
    }
}

A C++ solution by checking the longest common prefix string-by-string:

Starting from the second string, compare it with the first string, and update the longest common suffix found so far. This solution might be fast if the number of strings are much larger than the string lengths.

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
     if (strs.size() == 0) {
         return "";
     }
     int longest_common_prefix_len = strs[0].size();
     for (int i = 1; i < strs.size(); ++i) {
         for (int j = 0; j < longest_common_prefix_len; ++j) {
             if (strs[i][j] != strs[0][j]) {
                 longest_common_prefix_len = j;
             }
         }
     }
     return strs[0].substr(0,longest_common_prefix_len);
    }
};