最长公共前缀

**
 * 
 * @author Jacob
 *
 */
public class Demo1 {
	/*
	 * 对字符串数组进行排序，然后只要比较首尾两个字符串即可
	 */
	public String longestCommonPrefix(String[] strs) {
        StringBuilder result = new StringBuilder();
        
        if (strs!= null && strs.length > 0){
        
            Arrays.sort(strs);
            
            char [] a = strs[0].toCharArray();
            char [] b = strs[strs.length-1].toCharArray();
            
            for (int i = 0; i < a.length; i ++){
                if (b.length > i && b[i] == a[i]){
                    result.append(b[i]);
                }
                else {
                    return result.toString();
                }
            }
        return result.toString();
    }

	/*
	 * O(N^2)的解法
	 */
	public String longestCommonPrefix_1(String[] strs) {
		if (strs == null || strs.length == 0)
			return "";
		int len = strs.length;
		int min = strs[0].length();
		for (int i = 1; i < len; i++) {
			if (strs[i].length() < min)
				min = strs[i].length();
		}
		int res = -1;
		boolean flag = false;
		for (int i = 0; i < min; i++) {
			char tmp = strs[0].charAt(i);
			for (int j = 1; j < len; j++) {
				if (strs[j].charAt(i) != tmp) {
					flag = true;
					break;
				}
			}
			if (flag)
				break;
			res = i;
		}

		return strs[0].substring(0, res + 1);
	}
}

function longestCommonPrefix( strs ) {
    // write code here
    if (strs.length < 1) return '';
    if (strs.length === 1) return strs[0];
    strs.sort();
    const first = strs[0], end = strs[strs.length - 1];
    let res = '';
    for (let i = 0; i < first.length; i++) {
        if (first[i] !== end[i]) break;
        res += first[i];
    }
    return res;
}

class Solution {
private:
    string findCommonPrefix(const string& a,const string& b)
    {
        string res;
        int i = 0;
        int size = min(a.size(),b.size());
        while(i < size && a[i] == b[i])
            res += a[i++];
        return res;
    }
public:
    string longestCommonPrefix(vector<string> &strs) {
        if(strs.size() == 0)
            return string();
        string res = strs[0];
        for(int i = 1; i < strs.size() && res.size(); ++i)
            res = findCommonPrefix(res,strs[i]);
        return res;
    }
};

//字典树
public class Solution {
    class Node{
        int num  = 0 ; 
        Node[] next = new Node[26] ; 
        public void add(){
            num++ ; 
        }
    }
    int result = Integer.MAX_VALUE ; 
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0){
            return "" ; 
        }
        Node root = new Node() ; 
        int pos = 0 ; 
        result = strs[0].length() ; 
        for(String s:strs){
            result = Math.min(s.length(),result) ; 
            add(root,0,s,pos) ; 
            pos++ ; 
        }
        return strs[0].substring(0,result) ; 
    }
    
    public void add(Node root, int pos , String s,int needNum){
        if(pos == s.length()){
            return ; 
        }
        char c = s.charAt(pos) ; 
        int nn = (int)(c-'a') ; 
        if(root.next[nn] == null){
            root.next[nn] = new Node() ; 
        }
        if(root.next[nn].num != needNum){
            result = Math.min(result,pos) ; 
        }
        root.next[nn].num++ ; 
        add(root.next[nn],pos+1,s,needNum) ; 
    }
    
    
}

string longestCommonPrefix(vector<string> &strs) {
        int n=strs.size();
        if(n==0)
            return "";
        string prefix=strs[0];
        for(int i=1;i<n;i++){
            if(prefix.length()==0||strs[i].length()==0)
                return "";
            int len=std::min(prefix.length(),strs[i].length());
            int j;
            for(j=0;j<len;j++){
                if(prefix[j]!=strs[i][j])
                    break;
            }
            prefix=strs[i].substr(0,j);
        }
        return prefix;
    }

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
        if(strs.empty())return "";
        sort(strs.begin(),strs.end());
        int i=0,len=min(strs[0].size(),strs.back().size());
        for(;i<len;++i)
            if(strs[0][i]!=strs.back()[i])break;
        return strs[0].substr(0,i);
    }
};

// 只有好愚蠢的O(n^2)的算法.....
public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.length <= 0)
        	return "";
        
        String prefix = "";
        boolean isPrefix = true;
        for(int i = 0; i < strs[0].length(); i++){
        	String tmp = strs[0].substring(0, i + 1);
        	for(int j = 1; j < strs.length; j++){
        		if(strs[j].indexOf(tmp) != 0){
        			isPrefix = false;
        		}
        	}
        	if(isPrefix){
        		prefix = tmp;
        	}
        	else {
				break;
			}
        }
        return prefix;
    }
}

function longestCommonPrefix(strs) {

    strs = strs.sort()
    var str1 = strs[0]
    var str2 = strs[strs.length - 1]

    var index = 0
    var str = ""
    if (strs.length == 0) {
        return str 
    } else if (str2.startsWith(str1)) {
        return str1
    } 

    while (true) {
        if (str1[index] === str2[index]) {
            str += str1[index]
            index++         
        }else {
            break
        }
    }
    return str

}

一共有5种方法：

1.水平扫描法

2.垂直扫描法

3.分治算法

4.二分算法

5.前缀树/字典树（Prefix Tree）

/**
 * 
 * @author ChopinXBP
 * 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 "".
 * Note: All given inputs are in lowercase letters a-z.
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""。
 * 说明: 所有输入只包含小写字母 a-z 。
 *
 */

public class LongestCommonPrefix {

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        String[] strs = {"flower","flow","flight"};
        String[] strs2 = {"aa","aa"};
        String[] strs3 = {"a"};
        System.out.println(longestCommonPrefix(strs));
        System.out.println(longestCommonPrefix2(strs));
        System.out.println(longestCommonPrefix3(strs));
        System.out.println(longestCommonPrefix4(strs));
        System.out.println(longestCommonPrefix4(strs2));
        System.out.println(longestCommonPrefix4(strs3));
    }

    //水平扫描法：在线处理，不断调整公共前缀的长度
    public static String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0)
            return "";

        int maxcomidx = strs[0].length() - 1;
        for(int i = 1; i < strs.length; i++) {
            int idx = -1;
            while(idx < maxcomidx && idx < strs[i].length() - 1) {
                if(strs[0].charAt(idx + 1) == strs[i].charAt(idx + 1)) {
                    idx++;
                }else {
                    break;
                }
            }

            if(idx == -1) return "";
            maxcomidx = idx;
        }

        return strs[0].substring(0, maxcomidx + 1);
    }

    //垂直扫描法：按列扫描，先验证所有字符串的第一个元素
    public static String longestCommonPrefix2(String[] strs) {
        if (strs == null || strs.length == 0)
            return "";
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i == strs[j].length() || strs[j].charAt(i) != c)
                    return strs[0].substring(0, i);
            }
        }
        return strs[0];
    }

    //分治算法，在水平扫描法的基础上改进
    public static String longestCommonPrefix3(String[] strs) {
        if (strs == null || strs.length == 0)
            return "";

        return Solution(strs, 0, strs.length - 1);
    }

    public static String Solution(String[] strs, int begin, int end) {
        if(begin == end) {
            return strs[begin];
        }
        else {
            int mid = (begin + end) >> 1;
            String str1 = Solution(strs, begin, mid);
            String str2 = Solution(strs, mid + 1, end);
            if(str1 == "" || str2 == "") return "";

            int idx = -1;
            while(idx < str1.length() - 1 && idx < str2.length() - 1) {
                if(str1.charAt(idx + 1) == str2.charAt(idx + 1)) {
                    idx++;
                }else {
                    break;
                }
            }
            if(idx == -1) return "";
            return strs[begin].substring(0, idx + 1);
        }
    }

    //二分查找算法
    public static String longestCommonPrefix4(String[] strs) {
        if (strs == null || strs.length == 0)
            return "";

        int begin = 1;
        int end = strs[0].length();
        int maxcomidx = -1;

        while(begin <= end) {
            int mid = (begin + end) >> 1;
            if(isCommonPrefix(strs, mid)) {
                begin = mid + 1;
                maxcomidx = mid;
            }else {
                end = mid - 1;
            }
        }

        if(maxcomidx == -1) {
            return "";
        }else {
            return strs[0].substring(0, maxcomidx);
        }
    }

    public static boolean isCommonPrefix(String[] strs, int idx) {
        String prefix = strs[0].substring(0, idx);
        for(int i = 1; i < strs.length; i++) {
            if(!strs[i].startsWith(prefix)) {
                return false;
            }
        }
        return true;
    }

    //拓展：给定一些键值字符串 S = [S1……Sn]，我们要找到字符串 q与 S的最长公共前缀。
    //可以利用前缀树/字典树（Prefix Tree）
    //https://leetcode.com/articles/implement-trie-prefix-tree/
}

//先对字符串排序，然后考虑第一个和最后一个的首字符，这两个字符必定是差距最大的两个
//(因为排序首先从第一个开始排)，如果这两个不等，就返回空，否则，说明所有字符串的首
//字符相等，那么接着判断第二个。
class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
           if(!strs.size()) return "";
           sort(strs.begin(),strs.end());
           int i=0,sz=strs.size(),l=min(strs[0].size(),strs[sz-1].size());
           for(;i<l;i++)
               if(strs[0][i]!=strs[sz-1][i])
                  return strs[0].substr(0,i); 
           return strs[0].substr(0,l);
    }
};

class Solution {
public:
    string longestCommonPrefix(vector<string> &strs) {
  		if(strs.empty())
  			return "";
  		sort(strs.begin(),strs.end());
  		
  		int n = strs.size();
  		int l = min(strs[0].size(),strs[n-1].size());
  		for(int i=0;i<l;i++)
  			if(strs[0][i] != strs[n-1][i])
  				return strs[0].substr(0,i);
  		return strs[0].substr(0,l);
    }
};

class Solution:
    def longestCommonPrefix(self , strs: List[str]) -> str:
        if strs == []: return ""
        ms = min(strs)
        for s in strs:
            if s != ms:
                for i in range(len(ms)):
                    if ms[i] != s[i]:
                        ms = ms[:i]
                        break
        return ms

public String longestCommonPrefix (String[] strs) {
        if(strs.length==0) return "";
        String tmp=strs[0];
        for(int i=1;i<strs.length;i++){
            while(strs[i].indexOf(tmp)!=0){//如果返回的索引位置不是0
                tmp=tmp.substring(0,tmp.length()-1);

            }

        }
        return tmp;//一直在缩短tmp,直至缩短到公共前缀
    }

class Solution:
    def longestCommonPrefix(self , strs: List[str]) -> str:
        if not strs:
            return ''
        else:
            min_len = min([len(i) for i in strs])
            result = ""
            for j in range(min_len): 
                compare_list = [strs[i][j] for i in range(len(strs))]
                if len(set(compare_list)) == 1:
                    result += strs[0][j]
        return  result

    /*
    * 目的：最长公共前缀，类似合并多个有序链表
    * 方法1：递归
    * 方法2：以第一个为基准进行比较
    */
    string longestCommonPrefix(vector<string> &strs) {
        string res;
        if (strs.size()==0)
            return "";
        if (strs.size()==1)
            return strs[0];
        int i = 1;
        for (; i < strs.size();++i){
            if (strs[i].size()== 0 || strs[i-1].size()==0 || strs[i][0]!=strs[i-1][0]){
                return "";
            }
            else{
                strs[i-1]= strs[i-1].substr(1,strs[i-1].size()-1);
            }
        }
        res+=strs[i-1][0];
        strs[i-1] = strs[i-1].substr(1,strs[i-1].size()-1);
        res+=longestCommonPrefix(strs);
        return res;
    }
    //方法二
    string longestCommonPrefix(vector<string> &strs) {
        if (strs.size()==0)
            return "";
        for (int i = 0;i<strs[0].size();++i){
            for (int j = 1;j<strs.size();++j){
                if (strs[j][i] != strs[0][i])
                    return strs[0].substr(0,i);
            }
        }
        return strs[0];
    }

class Solution {
public:
    /**
     * 
     * @param strs string字符串vector 
     * @return string字符串
     */
    string longestCommonPrefix(vector<string>& strs) {
        // 时间复杂度O(N*len)，len是第一个字符串的长度，空间复杂度O(1)
        string res;
        if (strs.empty()) 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 (c != strs[j][i]) return res;
            }
            res += c;
        }
        return res;
    }
};