(Leet Code c++)Longest Common Prefix

14. Longest Common Prefix

 

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

 

Example 1:

Input: strs = ["flower","flow","flight"] Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings.

 

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.

 

주어진 문자열 벡터를 오름차순으로 정렬을 한 후 시작.

정렬된 strs에서 맨 앞에 있는 가장 짧은 문자열을 선택하여, prefix가 존재하는지 확인하도록 한다.

substr()을 이용해 문자열을 잘라 prefix에 저장한다.

그리고 1 ~ strs.size() 만큼 벡터를 순회하면서 0번째의 prefix와 j 번째의 prefix가 같은지 비교하면 된다.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string answer = "";
        
        sort(strs.begin(), strs.end());
        
        for(int i = 0; i < strs[0].size(); i++){
            string prefix = strs[0].substr(0, i + 1);
            bool check = true;
            
            for(int j = 1; j < strs.size(); j++){
                if(strs[j].substr(0, i + 1) != prefix){
                    check = false;
                    break;
                }
            }
            
            if(check){
                answer = prefix;
            }
        }
        
        return answer;
    }
};