14.最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

示例1.
输入: ["flower","flow","flight"]
输出: "fl"
示例2.
输入:["ca","a"]
输出: ""

暴力复杂度O(k*n)

第一个字符串长度:k
字符串个数:n
string:find

npos 是这样定义的：
static const size_type npos = -1;

c++ code:此代码代表：最长公共子串

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res = "";
        if (strs.empty())return res;
        vector<int>pos(strs.capacity(),-1);//初始化为capacity个-1
        for (int i = 0; i <strs[0].size() ; i++)
        {
            char c = strs[0][i];
             int flag = 0;
            for (int j = 1; j < strs.capacity(); j++)
            {
                if (strs[j].find(c, pos[j] + 1) !=-1)
                    pos[j]=strs[j].find(c, pos[j] + 1);
                else
                    flag = 1;
            }
            if (flag == 0)res += c;
        }
        return res;
    }
};

核心c++ code :最长公共前缀 AC 99.8% 签到

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res = ""; int flag = 0;
        if (strs.empty() )return res;
        if (strs.capacity() == 1)return strs[0];
        int minlen = 0;
        for (int i = 0; i < strs.capacity() - 1; i++)
        {
            if (strs[i].length() < strs[i + 1].length())
                minlen = strs[i].length();
            else
                minlen = strs[i+1].length();
        }

        for (int i = 0; i <minlen ; i++)
        {
            for (int j = 1; j < strs.capacity(); j++)
            {
                char c = strs[0][i];
                if (c != strs[j][i])
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1)break;
            else res += strs[0][i];
        }


        return res;
    }
};

最长公共前缀 ,完整c++代码：

#include<iostream>
#include<string>
#include<algorithm>
#include<vector>
#include<sstream>
#include<assert.h>
#include<math.h>


using namespace std;

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string res = ""; int flag = 0;
        if (strs.empty() )return res;
        if (strs.capacity() == 1)return strs[0];
        int minlen = 0;
        for (int i = 0; i < strs.capacity() - 1; i++)
        {
            if (strs[i].length() < strs[i + 1].length())
                minlen = strs[i].length();
            else
                minlen = strs[i+1].length();
        }

        for (int i = 0; i <minlen ; i++)
        {
            for (int j = 1; j < strs.capacity(); j++)
            {
                char c = strs[0][i];
                if (c != strs[j][i])
                {
                    flag = 1;
                    break;
                }
            }
            if (flag == 1)break;
            else res += strs[0][i];
        }


        return res;
    }
};

void trimLeftTrailingSpaces(string &input) {
    input.erase(input.begin(), find_if(input.begin(), input.end(), [](int ch) {
        return !isspace(ch);
    }));
}

void trimRightTrailingSpaces(string &input) {
    input.erase(find_if(input.rbegin(), input.rend(), [](int ch) {
        return !isspace(ch);
    }).base(), input.end());
}

vector<string> stringToStringVector(string input) {
    vector<string> output;
    trimLeftTrailingSpaces(input);
    trimRightTrailingSpaces(input);
    input = input.substr(1, input.length() - 2);
    stringstream ss;
    ss.str(input);
    string item;
    char delim = ',';

    while (getline(ss, item, delim)) {
        item = item.substr(1, item.length() - 2);
        output.push_back(item);
    }
    return output;
}

int main() {
    string line;
    while (getline(cin, line)) {
        vector<string> height = stringToStringVector(line);

        string ret = Solution().longestCommonPrefix(height);

         
        cout << ret << endl;
    }
    return 0;
}