Longest Common Prefix Solutions in C++

// Source : https://oj.leetcode.com/problems/longest-common-prefix/
// Author : Hao Chen
// Date   : 2014-07-03



#include <iostream>
#include <string>
#include <vector>
using namespace std;


string longestCommonPrefix(vector<string> &strs) {
    string word;
    if (strs.size()<=0) return word;
    for(int i=1; i<=strs[0].size(); i++){
        string w = strs[0].substr(0, i);
        bool match = true;
        int j=1;
        for(j=1; j<strs.size(); j++){
            if (i>strs[j].size() || w!=strs[j].substr(0, i) ) {
                match=false;
                break;
            }
        }
        if (!match) {
            return word;
        }
        word = w;
    }
    return word;
}

int main()
{
    const char* s[]={"abab","aba","abc"};
    vector<string> v(s, s+3);
    cout << longestCommonPrefix(v) <<endl;
}

#include <string> 
#include <vector>
using std::string; using std::vector;

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        if (strs.empty()) return "";
        for (size_t i=0; i<strs.front().size(); ++i) {
            for (const auto &str : strs)
                if (i == str.size() || str.at(i) != strs.front().at(i))
                    return strs.front().substr(0, i); 
        }
        return strs.front();
    }
};

/// Source : https://leetcode.com/problems/longest-common-prefix/description/
/// Author : liuyubobobo
/// Time   : 2018-06-03

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Vertical Scan
/// Time Complexity: O(len(strs) * max len of string)
/// Space Complexity: O(1)
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {

        string res = "";
        if(strs.size() == 0)
            return res;

        for(int i = 0 ; i < strs[0].size() ; i ++){

            char c = strs[0][i];
            for(int j = 1 ; j < strs.size() ; j ++)
                if(i >= strs[j].size() || strs[j][i] != c)
                    return res;

            res += c;
        }

        return res;
    }
};


int main() {

    vector<string> strs1 = {"flower","flow","flight"};
    cout << Solution().longestCommonPrefix(strs1) << endl;

    vector<string> strs2 = {"dog","racecar","car"};
    cout << Solution().longestCommonPrefix(strs2) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/longest-common-prefix/description/
/// Author : liuyubobobo
/// Time   : 2018-06-03

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Horizonal Scan
/// Time Complexity: O(len(strs) * max len of string)
/// Space Complexity: O(1)
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {

        if(strs.size() == 0)
            return "";

        string res = strs[0];

        for(int i = 1 ; i < strs.size() ; i ++){
            for(int j = 0 ; j < res.size() ; j ++)
                if(j >= strs[i].size() || res[j] != strs[i][j]){
                    res = res.substr(0, j);
                    break;
                }
        }

        return res;
    }
};


int main() {

    vector<string> strs1 = {"flower","flow","flight"};
    cout << Solution().longestCommonPrefix(strs1) << endl;

    vector<string> strs2 = {"dog","racecar","car"};
    cout << Solution().longestCommonPrefix(strs2) << endl;

    return 0;
}

/// Source : https://leetcode.com/problems/longest-common-prefix/description/
/// Author : liuyubobobo
/// Time   : 2018-06-03

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;


/// Divide and Conquer
/// Time Complexity: O(len(strs) * max len of string)
/// Space Complexity: O(log(len(strs)))
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {

        if(strs.size() == 0)
            return "";

        return solve(strs, 0, strs.size() - 1);
    }

private:
    string solve(const vector<string>& strs, int start, int end){

        if(start == end)
            return strs[start];

        int mid = (start + end) / 2;
        string res1 = solve(strs, start, mid);
        string res2 = solve(strs, mid + 1, end);

        int i = 0;
        for( ; i < res1.size() && i < res2.size(); i ++)
            if(res1[i] != res2[i])
                break;

        return res1.substr(0, i);
    }
};


int main() {

    vector<string> strs1 = {"flower","flow","flight"};
    cout << Solution().longestCommonPrefix(strs1) << endl;

    vector<string> strs2 = {"dog","racecar","car"};
    cout << Solution().longestCommonPrefix(strs2) << endl;

    return 0;
}