Leet me code 3 - [LeetCode][C++] 14. Longest Common Prefix (Easy)

leet me code :-)

---

https://leetcode.com/problems/longest-common-prefix/

Longest Common Prefix - LeetCode

 

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 배열에 있는 string들의 공통 prefix들 중 가장 긴 prefix는?

공통 prefix가 없는 경우 "" 리턴

 

 

생각의 흐름

앞에서부터 한 글자씩 검사해볼까...

첫 string을 prefix라 하고 앞에서부터 공통되는 글자 수 cnt로 저장, 가장 작은 값이 prefix

 

 

Solution Code

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        string prefix = strs[0];
        int min = prefix.length();
        for (auto str : strs) { 
            int cnt = 0;
            for (int i = 0; i < str.length(); ++i) {
                if (str[i] == prefix[i]) cnt++;
                else break;
            }
            min = min > cnt ? cnt : min;
        }
        
        if (min == 0) return "";
        
        string res = "";
        for (int i = 0; i < min; ++i) res += prefix[i];
        return res;
    }
};