LeetCode: 14번 (Longest Common Prefix) [JAVA]

문제 링크

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

Longest Common Prefix - LeetCode

풀이

전체적인 풀이 과정은 다음과 같다.

 

1. 주어진 strs 배열의 첫 번째 요소를 가져온 후 해당 단어가 가진 접두사 모음을 모두 HashSet에 저장
2. 그 이후 요소들을 돌며 현재 HashSet 속 접두사들과 비교를 하며 맞지 않은 접두사들의 경우 HashSet에서 삭제
3. 최종 후보군들만 남은 HashSet을 다시 돌며 가장 긴 접두사를 찾아 반환

 문제에서 요구하는 부분은 주어진 strs 배열 속 단어들 중 가장 긴 공통 접두사를 찾아 반환하는 문제이다. 그러기 때문에 주어진 strs 배열 속 첫 번째 단어를 꺼내 여기서 존재하는 모든 접두사 모음을 찾아 HashSet에 저장한다. 그 다음 for문을 통해 이후 단어들에서 해당 접두사들이 존재하는 지를 체크하며, 만약 존재하지 않은 접두사들의 경우 따로 저장해두었다가 기존 후보군이 모여있는 HashSet에서 제거를 한다.

 그렇게 탐색을 종료하고 HashSet을 다시 한 번 반복을 통해 찾으며 가장 긴 접두사를 찾아 반환하면 된다.

 

class Solution {
    public String longestCommonPrefix(String[] strs) {
        HashSet<String> candidates = new HashSet<>(); //접두사 후보군
        HashSet<String> temp = new HashSet<>();//삭제 접두사 임시 저장

        String answer = "";

        for (int i = 1; i <= strs[0].length(); i++) {//첫 번째 요소 속 접두사들 저장
            candidates.add(strs[0].substring(0, i));
        }

        for (int i = 1; i < strs.length; i++) {//이후 요소들을 돌며
            for (String prefix : candidates) {
                if (!strs[i].startsWith(prefix)) {//접두사가 맞지 않으면 삭제를 위해 표시
                    temp.add(prefix);
                }
            }

            for (String remove : temp) {//삭제할 접두사들을 제거
                candidates.remove(remove);
            }

            temp = new HashSet<>();
        }

        for (String prefix : candidates) {//이후 제일 긴 접두사를 찾아 반환
            if (prefix.length() > answer.length()) {
                answer = prefix;
            }
        }

        return answer;
    }
}

결과