<filename>src/2012-01-17_Longest_Common_Prefix.cpp
/*
 *
 * Copyright (c) 2014, weizhenwei
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * * Redistributions of source code must retain the above copyright notice, this
 *   list of conditions and the following disclaimer.
 * 
 * * Redistributions in binary form must reproduce the above copyright notice,
 *   this list of conditions and the following disclaimer in the documentation
 *   and/or other materials provided with the distribution.
 * 
 * * Neither the name of the {organization} nor the names of its
 *   contributors may be used to endorse or promote products derived from
 *   this software without specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
 * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 * File: 2012-01-17_Longest_Common_Prefix.cpp
 *
 *
 * Brief: https://oj.leetcode.com/problems/longest-common-prefix/
 * Write a function to find the longest common prefix string amongst an array of
 * strings.
 *
 *
 * Date: 2014.11.02
 *
 * Author: weizhenwei <<EMAIL>>
 *
 * *****************************************************************************
 */

#include <limits.h>
#include <stdio.h>
#include <string>
#include <set>
#include <vector>

using std::set;
using std::string;
using std::vector;

class Solution_Longest_Common_Prefix {
public:
    string longestCommonPrefix(vector<string> &strs) {
        if (strs.size() == 0) {
            return string("");
        }

        if (strs.size() == 1) {
            return strs[0];
        }

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

        string result;
        set<char> charset;
        result.clear();
        for (i = 0; i < minLength; i++) {
            int j = 0;
            string first = strs[0];
            charset.clear();
            charset.insert(charset.begin(), first[i]);
            for (j = 1; j < strs.size(); j++) {
                string tmp = strs[j];
                if (charset.find(tmp[i]) == charset.end()) {
                    return result;
                }
            }

            result.insert(result.begin() + result.size(), first[i]);
        }

        return result;
    }
};

static void print_strings(vector<string> &strs) {
    vector<string>::iterator iter;
    for (iter = strs.begin(); iter != strs.end(); iter++) {
        printf("%s\n", (*iter).c_str());
    }
    printf("\n");
}

int main(int argc, char *argv[]) {
    Solution_Longest_Common_Prefix solution;
    vector<string> strs;
    string result;

    strs.push_back("hello");
    strs.push_back("helo");
    strs.push_back("hehehe");
    strs.push_back("helol");
    result = solution.longestCommonPrefix(strs);
    print_strings(strs);
    printf("Longest Common Prefix:%s\n", result.c_str());

    strs.clear();
    strs.push_back("hello");
    result = solution.longestCommonPrefix(strs);
    print_strings(strs);
    printf("Longest Common Prefix:%s\n", result.c_str());

    strs.clear();
    strs.push_back("c");
    strs.push_back("c");
    result = solution.longestCommonPrefix(strs);
    print_strings(strs);
    printf("Longest Common Prefix:%s\n", result.c_str());


    return 0;
}
