题目

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: strs = ["flower","flow","flight"] Output: "fl" 

Example 2:

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

Constraints:

0 <= strs.length <= 200 0 <= strs[i].length <= 200 strs[i] consists of only lower-case English letters. 

LCP水平扫描获取相邻最大共同前缀

LCP数组(Longest Common Prefix Array)：是由后缀数组中相邻两个后缀的最长公共前缀的长度组成的数组。

首先，我们将描述一种简单的方法来查找一组字符串共享的最长前缀.LCP(S1…Sn).

我们得出如下规律

LCP(S1…Sn)=LCP(LCP(LCP(S1,S2),S3),…Sn)

![]

class Solution { public String longestCommonPrefix(String[] strs) { // check edge if (strs == null || strs.length == 0) { return ""; } if (strs.length == 1) { return strs[0]; } String preS = strs[0]; for(int i = 1; i < strs.length; i++) { while(strs[i].indexOf(preS) != 0) { preS = preS.substring(0, preS.length() - 1); if (preS.isEmpty()) { return ""; } } } return preS; } }