[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 "".

 

풀이

한 string을 기준으로 다른 모든 string의 i번째 글자가 전부 같은지 체크한다.

전부 같다면 계속해서 다음 글자를 확인하고, 다른 것이 있다면 현재까지의 답을 출력한다.

 

Time Complexity : $O(|S|)$

 

코드

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