算法|最长公共前缀

题目：编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1:

• 输入: [“flower”,“flow”,“flight”]
• 输出: “fl”

示例 2:

• 输入: [“dog”,“racecar”,“car”]
• 输出: “”
• 解释: 输入不存在公共前缀。

说明:所有输入只包含小写字母 a-z

Java代码

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        // 找到strs数组中长度最小的那个并放在首位,即str0
        String str0 = strs[0];
        for (int i = 1; i < strs.length; i++) {
            int minLen = Math.min(str0.length(), strs[i].length());
            if (minLen == strs[i].length()) {
                String strTemp = strs[i];
                strs[i] = str0;
                str0 = strTemp;
            }
        }
        
        // 从末尾向前遍历最短的字符串str0,并与数组内其他字符串相同位置的字符比较,若有不同则截取str0
        for (int j = str0.length() - 1; j >= 0; j--) {
            char tempChar = str0.charAt(j);
            for (int k = 1; k < strs.length; k++) {
                if (tempChar != strs[k].charAt(j)){
                    str0 = str0.substring(0,j);
                    break;
                }
            }
        }
        return str0;
    }
}
           

结果：

执行用时 :2 ms, 在所有 Java 提交中击败了87.98%的用户

内存消耗 :36.2 MB, 在所有 Java 提交中击败了86.93%的用户