最长公共前缀【LeetCode:14】

题目

编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。

• 示例 1:

输入: ["flower","flow","flight"]
输出: "fl"

• 示例 2:

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

• 说明:

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

解析

这道题很简单，将整个数组字符串视为一个左对齐的字符矩阵，顺着第一行（也就是一个字符串）遍历字符，依次判断每一列即可。

实现

java实现，用时1ms

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 特殊情况判断
        int length = strs.length;
        if (length == 0) {
            return "";
        } else if (length == 1) {
            return strs[0];
        }
        // 临时变量
        char lineChar, otherChar;
        // 将第一行视为每一列的第一个字符
        String line = strs[0];
        int count = 0, lineLength = line.length(), j;
        for (int i = 0; i < lineLength; i++, count++) {
            lineChar = line.charAt(i);
            for (j = 1; j < length; j++) {
                String other = strs[j];
                if (i >= other.length()) {
                    return line.substring(0, count);
                } else {
                    otherChar = other.charAt(i);
                    if (lineChar != otherChar) {
                        return line.substring(0, count);
                    }
                }
            }
        }
        return line.substring(0, count);
    }
}

来源：力扣（LeetCode）