题目详情

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

题目要求是，给定一个字符串的数组，我们要找到所有字符串所共有的最长的前缀。

想法

• 一种想法是先将数组的第一个元素赋值为前缀，然后不断找出它和后边的字符串所重叠的部分。（水平扫描）
• 但是这个方法有一个弊端，如果前面的元素特别长，而后面的元素又很短。就会产生较多的多余计算。
• 为了解决这个问题，可以每次都纵向对比每一个字符串相同位置的字符，找出最长的前缀。

解法一 水平扫描

public String longestCommonPrefix(String[] strs) {        if(strs == null || strs.length == 0)return "";        String prefix = strs[0];               if(strs.length ==1) return prefix;                for(int i=1;i

解法二 垂直扫描

public String longestCommonPrefix(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];}