【1】Longest Common Prefix(最长共同前缀)

[题目地址]https://leetcode.com/problems/longest-common-prefix/

题目概要:

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

• 在一个String的列表中找到最长的相同的前缀String.

思路1:

• 先将String列表进行排序, 然后只需要找出第一个String和最后一个String相同的前缀即可.

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        Arrays.sort(strs);
        StringBuilder result = new StringBuilder();
        char[] first = strs[0].toCharArray();
        char[] last = strs[strs.length - 1].toCharArray();
        
        for (int i = 0; i < first.length; i++) {
            if (last.length > i && last[i] == first[i]) {
                result.append(first[i]);
            } else {
                return result.toString();
            }
        }
        
        return result.toString();
    }
}

思路2:

• 取第一个String作为起始值，和下一个String进行比较，直到找到相同的前缀，遍历所有剩余的String.

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