[leet code] Longest Common Prefix

풀기 전 생각해보기

0 <= strs.length <= 200
0 <= strs[i].length <= 200

1) brute force
-> 2중 포문으로 비교
-> 최악의 경우 200 * 200

2) 정렬 후 가장 앞, 가장 뒤 문자열 비교
-> nlogn(정렬) + 2n(문자열 비교) => nlogn

코드

string longestCommonPrefix(vector<string> &strs){
    string answer = "";

    if (strs.size() == 0)
        return answer;
    sort(strs.begin(), strs.end());

    int min_len = 200;
    for (int i = 0; i < strs.size(); i++){
        if (strs[i].size() < min_len)
            min_len = strs[i].size();
    }

    int first_string = 0;
    int last_string = strs.size() - 1;
    if (min_len == 0)
        return answer;
    for (int i = 0; i < min_len; i++){
        if (strs[first_string][i] == strs[last_string][i])
            answer += strs[first_string][i];
        else
            return answer;
    }

    return answer;
}

결과

-> 처음에 strs.size() == 0 조건을 예외처리 안해서 null pointer exception 발생 (문제 조건에 strs.length == 0일 수 있기 때문에 예외처리 해야함)
-> 통과

다른 방법