14. Longest Common Prefix

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

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 "". Note: All given inputs are in lowercase letters a-z.

 

주어진 모든 문자열의 공통 부분을 찾는 것이므로,

각 문자열을 하나씩 훑으면서 맞지 않는 부분을 제거하면 되겠다는 생각이 들었다.

index 접근 에러가 발생하길래 'strs == null' 대신 'strs.length == 0'으로 수정했다.

문자열 길이 비교에는 Math.min( )을 사용했다.

java는 index를 그대로 사용하여 문자열의 한 문자에 접근할 수 없으며, charAt을 사용해야 한다.

 

아래는 초기 답안이다.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String answer = "";
        
        if (strs.length == 0) {
            return answer;
        } else {
            answer = new String(strs[0]);
        }
        
        for (String str : strs) {
            int shorterLength = Math.min(answer.length(), str.length());
            answer = answer.substring(0, shorterLength);
            
            for (int i = 0; i < shorterLength; i++) {
                if (answer.charAt(i) != str.charAt(i)) {
                    answer = answer.substring(0, i);
                    break;
                }
            }
        }
        return answer;
    }
}

 

approach 1: horizontal scanning

수평 탐색은 위의 방식과 유사한데, 

LCP(Longest Common Prefix)를 첫 번째 요소부터 누적해가면서 모든 요소와 비교해가며 결론을 내는 것이다.

중간에 결론이 나지 않는다면 O(S)의 시간이 걸린다. (S: 모든 문자열의 모든 글자의 개수)

 

코드를 간단히 줄일 수 있는 방법으로 indexOf 메소드를 사용했는데,

특정 문자가 아닌 문자열을 기준으로 검색할 수도 있었다.

일치하는 첫 번째 index를 반환하며, n 번째 일치하는 index를 내도록 지정할 수도 있고,

해당 문자열이 없다면 -1을 반환한다.

String prefix = strs[0];

for (int i = 1; i < strs.length; i++) {
	while (strs[i].indexOf(prefix) != 0) {
    	prefix = prefix.substring(0, prefix.length() - 1);
        
        if (prefix.isEmpty()) {
        	return "";
        }
    }
}
return prefix;

 

 

approach 2: vertical scanning

두 번째 방법은 수직 탐색이다.

이 방법은 길이가 짧은 문자열이 다수 포함된 경우 연산 속도에 이점이 있다. (n * minLen)

방법은 간단하므로 생략한다.

 

 

approach 3: divide and conquer

세 번째 방법은 주어진 문자열을 쌍으로 나누어 각 쌍에서 LCP를 합쳐가며 구하는 방식이다.

merge sort 방식과 유사하다.

항목이 두 개 남았을 때부터 비교하여 CP를 찾아 반환하도록 한다.

딱히 크게 시간, 공간적 이득이 있는 것 같지는 않다.

class Solution {
    private String divideAndConquer (String[] strs, int left, int right) {
        if (right == left + 1) return strs[left];
        
        else {
            String str1 = null;
            String str2 = null;
            
            if (right == left + 2) {	// only 2 strings
                str1 = strs[left];
                str2 = strs[right - 1];
            }
            else if (right > left + 2) {	// more than 2 strings
                str1 = divideAndConquer(strs, left, (left + right) / 2);
                str2 = divideAndConquer(strs, (left + right) / 2, right);
            }
            int shorterLen = Math.min(str1.length(), str2.length());
            
            for (int i = 0; i < shorterLen; i++) {
                if (str1.charAt(i) != str2.charAt(i)) return str1.substring(0, i);
            }
            return str1.substring(0, shorterLen);
        }
    }
    
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        
        return divideAndConquer(strs, 0, strs.length);
    }
}

 

 

approach 4: binary search

네 번째 방법은 재밌게도 binary search 방식으로 답안을 찾는다.

한 문자열을 반으로 잘라가며 앞의 절반을 나머지 모든 문자열과 비교한다.

CP라고 판별된 경우 뒤의 절반에 대해서 위 과정을 반복하고,

CP가 아니라고 판별된 경우 앞을 다시 절반으로 나누어 위 과정을 반복한다.

더 이상 앞 또는 뒤의 문자열을 자를 수 없는 경우, 앞 쪽의 문자열이 LCP가 된다.

 

처음에는 맨 마지막 요소를 pivot으로 설정한 후 배열의 크기를 1 줄여 length 메소드를 사용하기 용이하게 하려 했으나,

생성된 배열의 크기를 줄이는 것은 불가능하여 첫 번째(index 0) 요소를 pivot으로 설정하기로 했다.

pivot 문자열에 대해 이미 비교를 마쳐 CP라고 판별된 부분을 base로, 한계 부분을 limit로 설정하고,

중간값을 looking으로 설정하여 binary search를 수행한다.

 

어려웠던 점은, 남은 문자열을 절반씩 늘리거나 줄이며 연산을 수행하는데,

최종적으로 남는 부분이 한 개인 경우의 예외 처리에 문제가 많이 발생했다.

looking을 중간값의 소수점 버림이 아닌 올림으로 설정하고 limit를 looking - 1로 수정한 뒤,

limit == base일 때 substring을 반환하여 문제를 해결했다.

사실 깔끔하게 디자인해서 알고리즘을 설계했다기 보다는,

test case를 몇 개 설정해두고 값이 들어맞도록 코드를 계속 수정했다는 점에서 아쉽다.

class Solution {
    private String binarySearch(String[] strs, int base, int limit) {
        String pivot = strs[0];
        int looking = (int)Math.ceil((base + limit) / 2.0);
        String lookingString = pivot.substring(0, looking);
        
        if (limit == base) return pivot.substring(0, limit);
        
        for (String str : strs) {
            if (str.indexOf(lookingString) != 0) {
                limit = looking - 1;
                return binarySearch(strs, base, limit);
            }
        }
        base = looking;
        return binarySearch(strs, base, limit);
    }
    
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        
        String pivot = strs[0];
        return binarySearch(strs, 0, pivot.length());
    }
}