[알고리즘] Longest Common Prefix

문제 정보

출처 : leetcode
난이도 : easy

[문제]
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 "".

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

내풀이

첫번째 str의 첫글자 'f'부터 모든 strs를 돌면서 공통인지 찾고 공통이라면 result에 넣어주고, 아니라면 result를 return하도록 구현하였다.

firstStr 길이만큼 for문을 돌고, 그 안에서 strs 길이만큼 for문을 돌기 때문에
시간복잡도는 O(S⋅m)이다.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String firstStr = strs[0];
        String result = "";

        for (int i = 0; i < firstStr.length(); i++) {
            String checkValue = firstStr.substring(i, i+1);

            for (String str : strs) {
                if (str.length() <= i ) {
                    return result;
                }
                if (!checkValue.equals(str.substring(i, i+1))) {
                    return result;
                }
            }

            result += checkValue;
        }

        return result;
    }
}

Runtime : 2 ms
Memory : 43.1 MB

개선하기

1. 일단 안되는 경우를 return해줘야하는데 빼먹었다.
   strs == null 이거나 strs.length == 0인 경우 볼것도 없이 ""를 return 해줘야한다.

2. 이진탐색으로 해결하면 시간복잡도가 더 줄어든다. prefix를 반씩 나눠가며 찾는다.

이진탐색을 사용해서 시간복잡도는 O(S⋅logm)이 되었다.

[출처]https://leetcode.com/problems/longest-common-prefix/editorial/

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }
        
        int minLen = Integer.MAX_VALUE;
        for (String str : strs) {
            minLen = Math.min(minLen, str.length());
        }

        int low = 1;
        int high = minLen;

        while (low <= high) {
            int middle = (low + high) / 2;

            if (isCommonPrefix(strs, middle)) {
                low = middle + 1;
            } else {
                high = middle - 1;
            }
        }

        return strs[0].substring(0, (low + high) / 2);
    }

    private boolean isCommonPrefix(String[] strs, int len) {
        String checkStr = strs[0].substring(0, len);

        for (String str : strs) {
            if (!str.startsWith(checkStr)) {
                return false;
            }
        }

        return true;
    }
}

Runtime : 0 ms
Memory : 40.2 MB

이진탐색으로 개선하니 시간복잡도, Runtime, Memory 다 개선되었다.