[LeetCode - 14] Longest Common Prefix- Java

문제 설명

문제

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"

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

 

제한사항

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.

 

풀이 : Success

소스 코드

class Solution {
    public String longestCommonPrefix(String[] strs) {
        String prefix = strs[0];
        String str = strs[0];
        for (int i = 1; i < strs.length; i++) {
            prefix = "";
            for (int j = 0; j < getMinLength(str, strs[i]); j++) {
                if(str.charAt(j) == strs[i].charAt(j)){
                    prefix += str.charAt(j);
                }
                else break;
            }
            str = prefix;
        }

        return prefix;
    }
    
    public int getMinLength(String strA, String strB){
        return strA.length() < strB.length() ? strA.length() : strB.length();
    }
}​

 

풀이 회고

우선 입력받은 문자열 배열 중 첫번째 원소를 별도 변수(prefix, str)에 저장하도록 했는데 prefix에 저장한 이유는 단 하나의 문자열 배열만 입력으로 오는 경우 이를 바로 return 시키기 위함이고, str에 저장한 이유는 다음 문자열과 중복되는 접두사를 비교하기 위함이다.

 

2개 이상의 문자열 배열이 들어오는 경우에만 for문이 실행되는데, 이때 앞서 저장했던 prefix를 ""로 초기화 시키고 처음 문자열과 나중 문자열 길이 중 가장 작은 길이를 반환받아(getMinLength 메서드) 이를 통해 중첩 for문을 실행시켰다.

 

이후 현재 문자열(str)과 그 다음 문자열(strs[i])의 문자 하나하나씩 비교하여 일치하면 결과값 prefix에 추가하고, 일치하지 않으면 해당 for문으로부터 break 했다. break 이후 str 변수에 prefix를 저장시키도록 했는데, 해당 문제는 공통된 prefix를 찾는 것이므로 일치하지 않는 문자는 굳이 비교할 필요도 없기 때문이다.

 

모범 소스코드

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) return "";
        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;
	}
}

 

코드 분석

위 풀이는 리트코드 내 수많은 모범 답안 중 하나이다. 나의 풀이 보다 훨씬 간결하다.

 

해당 풀이에서는 우선 입력받는 문자열 배열의 크기가 0인 경우 ""을 return하도록 하고있지만 사실 문제 조건에서 문자열 배열의 크기는 1 이상이므로 불필요한 코드로 보인다.

 

이후 내 풀이와 동일하게 prefix에 첫번째 문자열을 저장하도록 했고 마찬가지로 2개 이상의 문자열이 있을때만 for문이 실행되도록 했다.

 

하지만 이 풀이에서의 주요 특징은 문자열의 indexOf 메서드와 substring 메서드를 사용하고있는 점이다. 우선 나중 문자열(strs[i])의 접두사와 prefix 변수 문자열(첫번째 문자열)이 일치하는지를 검사(strs[i].indexOf(prefix) != 0)한 후 일치하지 않으면 prefix 변수 문자열의 마지막 문자를 하나씩 제거(prefix = prefix.substring(0, prefix.length() - 1))해가면서 다시 일치하는 접두사를 검사하도록 했다.

 

특정 문자열 검사 시 아무것도 겹치지 않으면 ""을 반환시켰고 모든 문자열 배열을 완전 탐색하며 최종적으로 겹친 접두사 prefix를 반환시키도록 했다.

 

위 풀이를 통해 내가 작성한 알고리즘의 문제점은 특정 문자열 검사 시 아무것도 겹치지 않는 경우 ""이 즉각 return 됐어야 했는데 필요없이 모든 문자열 배열을 탐색한다는 점 그리고 겹치는 접두사를 별도로 저장하지 않고 다시 처음부터 접두사를 일일이 검사한다는 점임을 알 수 있었다.

 

 

참고자료

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