Search This Blog

Tuesday, December 18, 2012

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);
    }
};

3 comments:

Anonymous said...

wtf man this is so wrong, go fix it brah

Anonymous said...

sorry i take it back, your solution is elegant

Anonymous said...

Java solution is too slow. loop over all the array so many times.