C++ Coding Exercise – Longest Common Prefix


Write a function to find the longest common prefix string amongst an array of strings. For example, [“aa”, “a”] should return “a”. The common prefix length should not exceed the minimal string length in the vector. And all we need to do is to check each character from the start to see if they appear in all strings. Return the substring if any mis-match found.

This is a O(MN) solution that M is the least number of the string length and N is the number of strings in the array.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = INT_MAX;
        if (strs.size() <= 0) {
            return "";
        }
        if (strs.size() == 1) {
            return strs[0];
        }
        // get the min length
        for (int i = 0; i < strs.size(); i ++) {
            n = strs[i].length() < n ? strs[i].length() : n ;
        }
        for (int i = 0; i < n; i ++) { // check each character
            for (int j = 1; j < strs.size(); j ++) {
                if (strs[j][i] != strs[j - 1][i]) { // we find a mis-match
                    return strs[0].substr(0, i);
                }
            }
        }
        // prefix is n-length
        return strs[0].substr(0, n);
    }
};
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int n = INT_MAX;
        if (strs.size() <= 0) {
            return "";
        }
        if (strs.size() == 1) {
            return strs[0];
        }
        // get the min length
        for (int i = 0; i < strs.size(); i ++) {
            n = strs[i].length() < n ? strs[i].length() : n ;
        }
        for (int i = 0; i < n; i ++) { // check each character
            for (int j = 1; j < strs.size(); j ++) {
                if (strs[j][i] != strs[j - 1][i]) { // we find a mis-match
                    return strs[0].substr(0, i);
                }
            }
        }
        // prefix is n-length
        return strs[0].substr(0, n);
    }
};

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
223 words
Last Post: The Permutation Algorithm for Arrays using Recursion
Next Post: Combination Algorithm by Iterative Backtracking Algorithm

The Permanent URL is: C++ Coding Exercise – Longest Common Prefix

Leave a Reply