문자열 배열 중에서 가장 긴 공통 접두사 문자열에 대한이 솔루션의 시간 복잡도는 얼마나됩니까?

Question

이것은 문제 문장입니다. -

문자열 배열 중에서 가장 긴 공통 접두사 문자열을 찾는 함수를 작성하십시오.

내 솔루션의 시간 복잡성에 대해서는 잘 모르겠습니다. 나는 그것을 추측하고있다 O (nmnlogn). 정렬을위한 nlogn과 배열을 반복하기위한 n * m, 그리고 문자열에 대해 m 개의 비교를하는 것.

string longestCommonPrefix(vector<string>& strs) { 
    if(strs.size() == 0) return ""; 

    sort(strs.begin(), strs.end()); 

    string prefix = strs[0]; 
    int length = prefix.length(); 
    for (int i = 0; i < strs.size(); ++i) { 
     if (prefix == strs[i].substr(0, length)) continue; 
     if (prefix != strs[i].substr(0, length)) { 
      prefix = prefix.substr(0, --length); 
      length = prefix.length(); 
      i = 0; 
     } 
     if (prefix == "") break; 
    } 

    return prefix; 
} 

Answer 1

정렬 후 모든 O (나노 미터) 인 것을 가정하면, 다음이 될 것이다 O (nlogn + 나노 미터)을 할 수도 있습니다 (당신이 정렬 한 번만를하고 있기 때문에) 단순화 추가에 기반한다 m과 logn 사이의 관계.