[LeetCode] 14. Longest Common Prefix

풀이.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string answer = "";
         size_t shortest_length = strs[0].length(); // 첫 번째 문자열의 길이로 초기화

    for (const auto& str : strs) {
        shortest_length = std::min(shortest_length, str.length());
    }

        for(int i = 0 ; i < shortest_length; i++){
            char firstStr = strs[0][i];
            for(int j = 1 ; j < strs.size(); j++){
                // std::cout << i << j << ":" <<strs[j][i] << std::endl;
                if(firstStr != strs[j][i]){
                    return answer;
                }
            }
            answer += firstStr;
        }
        return answer;
    }
};

먼저 strs중 가장 길이가 작은 문자열을 뽑는다.
이유는 문자열로 들어온 모든 값이 공통되어야 하며 3자리 2자리 3자리가 들어왔을 때 최대 공통될 수 있는 문자열의 갯수는 2개 이기 때문이다.

이후 가장 작은 문자열을 시작으로 다른 문자열의 자리수를 비교한다. 만약 하나라도 다르다면 곧바로 answer를 return하고 반복문을 빠져나오면 현재 문자열을 answer에 더해줘서 풀었다.

---

솔루션.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        std::sort(strs.begin(), strs.end());
        if (strs.size() == 1) {
            return strs[0];
        }
        if (strs[0] == strs[strs.size() - 1]) {
            return strs[0];
        }
        for (int i = 0; i < strs[0].length(); i++) {
            if (strs[strs.size() - 1][i] != strs[0][i]) {
                return strs[0].substr(0, i);
            }
        }
        return strs[0];
    }
};

(https://leetcode.com/problems/longest-common-prefix/solutions/4908025/c-easy-solution/)

이 사람이 푼것을 보면 sort를 통해 문자열의 길이중 가장 작은것을 찾고 사이즈가 1이거나, 0번째 인덱스와 마지막 인덱스 문자가 같다면 곧바로 strs의 첫번째를 리턴한다.

이후 맨 첫번째와 맨 마지막 배열의 문자열을 하나하나 비교하며 다른 녀석을 substr로 하나씩 빼준다.