LeetCode 14：Longest Common Prefix

一个函数，传入一个字符串数组，返回所有数组元素里公共前缀的最长子串

可以以第一个字符串为基准，遍历strs[0]的所有字符，然后每次拿字符和同位置的其它字符串的字符进行对比，如果有不相同的，前面的子串即为所求

但是很容易少了一个条件，当strs[0]不是最短的字符串时候，如果前面都一样，肯定有其它字符串先遍历到末尾，这时候应该就直接返回，否则就越界

package com.maoxiaomeng;

/**
 * @author lihui
 * @date 2018/3/26 12:31
 */

public class Solution {
    /**
     * "lihuia", "lihuib", "lihuiab", "lihuic"
     * 
     * l i h u i a
     * l i h u i b
     * l i h u i a b
     * l i h u i c
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            for (int index = 1; index < strs.length; index++) {
                if (i == strs[index].length() || c != strs[index].charAt(i)) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0]; 
    }
}

另一种更简单的方法，同样以第一个字符串元素为基准，先看整个字符串strs[0]是否在其它字符串中，然后去掉最后一个字符验证，然后去掉最后两个，……，直到substring在所有的字符串前缀里

Java源码如下

package com.maoxiaomeng;

/**
 * @author lihui
 * @date 2018/3/26 12:31
 */

public class Solution {
    /**
     * "lihuia", "lihuib", "lihuiab", "lihuic"
     * @param strs
     * @return
     */
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String maxStr = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(maxStr) != 0) {
                maxStr = maxStr.substring(0, maxStr.length() - 1);
            }
        }
        return maxStr; 
    }
}

比较直接