[C++] LeetCode - Longest Common Prefix

딱히 어떤 자료구조나 알고리즘을 사용할지 애매한 문제인 것 같습니다. 그저 완전탐색처럼 다 보는 수밖에 없겠다 싶은 문제같아요. 문제는 직관적이고 딱히 어렵지 않습니다.

---

문제 정의

---

---

접근 방법

• 모든 원소들에 대해 첫 문자부터 지켜보면서 같은지 판별합니다. 만약 하나라도 다른 케이스가 발생한다면, 그 전의 문자까지만 정답에 집어넣습니다.
• 가장 길이가 짧은 원소를 구하고, 그 길이 만큼만 while loop이 실행되도록 합니다.
• 만약 문자열 1개만 주어졌을 경우, 그 자체가 정답이 되므로 while loop이 돌기 전에 return 합니다.

---

결과

웬일인지 다른 제출안들보다 비교적 좋은 평가를 받았네요. 너무 별거 없어서 고수들이 참여를 안했나봅니다..

• Runtime: 3 ms, faster than 75.16% of C++ online submissions for Longest Common Prefix.
• Memory Usage: 9.2 MB, less than 43.90% of C++ online submissions for Longest Common Prefix.

---

코드

---

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        
        string answer = "";
        
        if (strs.size() == 1) {
            // if only 1 string exists,
            answer = strs[0];
            return answer;
        }
        
        int cnt = 0;
        int minLen = 300;
        for (int i=0; i < strs.size(); i++) {
            if (strs[i].size() < minLen) {
                minLen = strs[i].size();
            }
        }
        
        
        bool noMore = false;
        while(cnt != minLen) {
            
            
            for (int i=0; i < strs.size()-1; i++) {
                if (strs[i][cnt] != strs[i+1][cnt]) {
                    // not same prefix
                    noMore = true;
                    break;
                } else {
                    if (i==strs.size()-2) {
                        answer += strs[i][cnt];
                    }
                }
            }
            
            cnt++;
            if (noMore) {
                // reached maximum index
                break;
            }
            
        }
        
        return answer;
    }
};

---