0014._Longest_Common_Prefix.md

14. Longest Common Prefix

难度:Easy

刷题内容

原题连接

• https://leetcode.com/problems/longest-common-prefix/

内容描述

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

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"
Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.
Note:

All given inputs are in lowercase letters a-z.

思路1 - 时间复杂度: O(n^2)- 空间复杂度: O(1)******

求最长前缀公共子串，只有遍历所有子串，求出最长公共子串即可，不过要注意可能存在空字符串

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {            
        string temp;
        if(!strs.size() || !strs[0].length())
            return temp;
        int j = 0;
        while(1)
        {
            int i = 0;
            int ch = strs[0][j];
            for(;i < strs.size();++i)
                if(j >= strs[i].length() || strs[i][j] != ch)
                    break;
            if(i != strs.size())
                break;
            temp.push_back(strs[0][j++]);
        }
        return temp;
    }
};