leetcode14.最长的公共前缀

题目链接

题目描述：

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

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

示例 1:

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

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

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

题解：遍历

对给定的字符串数组的第一个字符串作为标准，让后面所有的字符串依次与其进行比对，当对两个字符串进行比较时，通过判断两个字符串的每个索引的字符是否相等即可判断出公共前缀；如果说比对的过程中出现了不相等的情况，即中断循环，更新前缀字符串为:
res = res.substring(0,index)。 代码如下：

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if(strs.length == 0) {
            return "";
        }

        String res = strs[0];
        for(int i =1;i<strs.length;i++) {
            int j=0;
            for(;j < res.length() && j < strs[i].length();j++) {
                if(res.charAt(j) != strs[i].charAt(j))
                    break;
            }
            res = res.substring(0, j);
            if(res.equals(""))
                return "";
        }
        return res;
    }
}

时间复杂度：O(n * m)，其中n为字符串数组的个数，m为每个字符串的长度

额外空间复杂度：O(1)

代码执行结果：