Find the longest common prefix in an array of strings (Longest Common Prefix)

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

Thoughts:
Apparently this can be done in O(n). We start with the first string as the longest common prefix. We then go through every string in the array and compare the prefix with them. Update (shorten) the prefix if needed.

Code (Java):

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        String prefix = new String();
        if(strs.length > 0)
            prefix = strs[0];
        for(int i = 1; i < strs.length; ++i) {
            String s = strs[i];
            int j = 0;
            for(; j < Math.min(prefix.length(), s.length()); ++j) {
                if(prefix.charAt(j) != s.charAt(j)) {
                    break;
                }
            }
            prefix = prefix.substring(0, j);
        }
        return prefix;
    }
}

Code (C++):

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        string prefix;
        if(strs.size() > 0)
            prefix = strs[0];
        for(int i = 1; i < strs.size(); ++i) {
            string s = strs[i];
            int j = 0;
            for(; j < min(prefix.size(), s.size()); ++j) {
                if(prefix[j] != s[j])
                    break;
            }
            prefix = prefix.substr(0, j);
        }
        return prefix;
    }
};
Advertisements

1 Comment (+add yours?)

  1. zenzen
    May 29, 2013 @ 07:22:11

    Old post I know but since I am preparing for an interview I will just say this isn’t O(n) but O(n*m) in the worst case (for instance n identical strings of length m) – at every loop iteration you will have to compare m characters and you will have n-1 iterations.

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: