请问这段求解最长公共前缀的Java代码的时间复杂度是多少？

题目描述 #

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

示例1 #

• 输入：strs = ["flower","flow","flight"]
• 输出："fl"

实现代码 #

class Solution {
    public String longestCommonPrefix(String[] strs) {
    if(strs==null || strs.length ==0){
        return "";
    }
 
    if(strs.length == 1){
        return strs[0];
    }
 
    int i=0;
    while(true){
        boolean flag = true;
        for(int j=1; j<strs.length; j++){
            if(strs[j].length()<=i || strs[j-1].length() <=i 
               || strs[j].charAt(i) != strs[j-1].charAt(i)){
                flag = false;
                break;
            }               
        }
 
        if(flag){
            i++;
        }else{
            break;
        }
    }
 
    return strs[0].substring(0, i);
  }
}

时间复杂度分析 #

这段代码的时间复杂度是O(m*n)，其中：

• m 是字符串数组中最长公共前缀的长度（若不存在公共前缀则为0）
• n 是字符串数组的元素个数

具体说明： #

1. 外层while循环会逐个检查公共前缀的字符位置，最多执行m次，直到出现不匹配字符或某个字符串遍历完毕。
2. 内层for循环会遍历数组中除第一个元素外的所有字符串，每次执行n-1次比较操作，整体接近n次。
3. 每次循环内的字符比较、长度判断都是O(1)操作，因此整体时间复杂度为两者的乘积O(m*n)。

最坏场景下，比如所有字符串完全相同，此时m等于字符串的长度，循环会执行m次，每次遍历n个字符串，时间复杂度同样为O(m*n)。

内容的提问来源于stack exchange，提问作者Chinmay