Leet Code - 14. Longest Common Prefix

처음 풀이는 첫 번째 단어를 기준으로 삼아서 다음 단어들과 비교한다.

첫 번째 단어의 각 문자와 다음 단어들의 해당 위치 문자가 모두 동일한지 확인 후, 동일하지 않을 경우 바로 break해서 반환하도록.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.size() == 1) {
            return strs[0];
        }
        int i;
        bool flag = false;;
        for (i = 0; i < strs[0].size(); i++) {
            char cur = strs[0][i];
            for (auto j: strs) {
                if (i == j.size() || j[i] != cur) {
                    flag = true;
                    break;
                }
            }
            if (flag) break;
        }
        return strs[0].substr(0, i);;
    }
};

그리고 해설을 보니까 이렇게 break해서 flag 설정 후 반환할 필요 없이 바로 반환하면 되는 거였다.

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

 

풀이는 비슷했는데 바로 반환하는 게 더 빠르고 메모리도 덜 사용했다.