[LeetCode/JAVA] 14. Longest Common Prefix

https://github.com/ROUTINE-STUDY/Algorithm

ROUTINE-STUDY/Algorithm

알고리즘 스터디를 진행하고 있습니다.
초보들로 구성되어있으며, 열심히 풀어보고 풀이 방식을 공유하고 피드백을 해주는 스터디입니다.
문의는 댓글 혹은 GitHub 주소를 참고해주세요.

---

문제 출처 : https://leetcode.com/problems/longest-common-prefix/

Longest Common Prefix - LeetCode

문제 설명

출처 : LeetCode

문자열 배열 중에서 가장 긴 공통 접두어를 찾아 반환하세요.
만약 공통 접두어가 없다면 빈 문자열("")을 반환하세요.

풀이 방법

개인적으로 마음에 드는 코드는 아니지만,  처음 접근방식을 기록합니다.
1. 반복문을 최소화하기 위해 문자열의 길이 내림차순으로 배열을 정렬
2. 첫 번째 문자열을 기준이 되는 문자열(standard)로 지정
3. 비교 대상 문자열을 standard와 같은 인덱스로 자른 후 동일한지 판단
4. 하나라도 다르다면 flag값을 false로 변경
5. flag가 true, 즉 모두 같다면 standard 문자열 return

내 코드(JAVA)

 

public String longestCommonPrefix(String[] strs) {
    String res = "";

    // 문자열 길이가 작은 순으로 내림차순 정렬
    Arrays.sort(strs, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            if(o1.length() > o2.length()) return 1;
            if(o1.length() < o2.length()) return -1;
            return 0;
        }
    });

    // 기준이되는 첫 번째 문자열
    StringBuilder standard = new StringBuilder(strs[0]);            
    for(int i=standard.length()-1; i>=0; i--) {
        // 일치하는지 확인하기 위한 flag 값
        boolean isEquals = true;                                    

        for(int j=1; j<strs.length; j++) {
            // 기준과 똑같은 인덱스로 잘라낸 문자열
            String str = strs[j].substring(0, standard.length());

            // 같은지 판단 후 하나라도 다르다면 flag false 후 break
            if(!str.equals(standard.toString())) {                  
                isEquals = false;
                break;
            }
        }

        // 모두 같다면 return value 저장 후 break
        if(isEquals) {                                              
            res = standard.toString();
            break;
        }
        // 기준 문자열 꼬리부터 하나씩 제거
        standard = standard.deleteCharAt(i);                        
    }

    return res;
}

다른 사람 풀이

 

// LeetCode Site 답안
// https://leetcode.com/problems/longest-common-prefix/discuss/6910/Java-code-with-13-lines
public String longestCommonPrefix(String[] strs) {
    if(strs == null || strs.length == 0)    return "";
    String pre = strs[0];
    int i = 1;
    while(i < strs.length){
        while(strs[i].indexOf(pre) != 0)
            pre = pre.substring(0,pre.length()-1);
        i++;
    }
    return pre;
}

indexOf 메서드를 활용할 생각을 하지 못하였다.

안쪽 while문 조건으로 활용하여 코드를 최소화하였고, 접두어가 다르다면 꼬리부터 하나씩 자르는 방식이다.

문자열 관련 문제는 좀 더 다양한 방법을 열어두고 생각한 후 풀어야겠다.