有人可以告诉我这段代码的时间复杂度是多少吗？

Question

Leetcode 问题：

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

如果没有公共前缀，则返回空字符串“”。

示例1：

输入：strs = [“花”,“流”,“飞行”] 输出：“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);
  }
} ```

Answer 1

我还没有检查你的算法的正确性，但这里最糟糕的情况是所有字符串都相等，并且由于这是一个嵌套循环，它会归结为

O(n * m)

，其中

n = str[0].length

和

m = str.length

。

外循环遍历每个字符位置，内循环遍历数组中的每个字符串。在最坏的情况下，

flag

永远不会设置为 false，因此它会运行整个过程。