14. Longest Common Prefix

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

ROUTINE-STUDY/Algorithm

문제 출처

Longest Common Prefix - LeetCode

[문제 설명]

*접두사를 구하시오. *

[처음 생각한 접근 방법]

1.가장 짧은 문자열을 구한다.

2.방금 구한 가장 짧은 문자열의 문자 하나와 나머지 문자열들의 문자를 비교한다.

3.같으면 prefix에 추가해준다.

class Solution {
    public String longestCommonPrefix(String[] strs) {
        StringBuilder answer = new StringBuilder();
        String shortestStr = strs[0];

        //가장 짧은 문자열 구하기.
        for (String str : strs) {
            if (str.length() < shortestStr.length()) {
                shortestStr = str;
            }
        }

    //가장 짧은 문자열을 기준으로
        //나머지 문자열들의 각 문자를 비교.
        for (int i = 0; i < shortestStr.length(); i++) {
            boolean isAllSame = true;
            char prefixChar = shortestStr.charAt(i);

            for (String str : strs) {
                if (str == shortestStr) {
                    continue;
                }
                if (str.charAt(i) != prefixChar) {
                    isAllSame = false;
                    break;
                }
            }
        //문자가 같지 않으면
            //그 문자는 prefix가 아님 -> 나머지 비교 필요x
            if (!isAllSame) {
                break;
            }
            //문자가 같으면 그 문자를 전부 prefix에 붙여줌.
            answer.append(prefixChar);
        }

        return answer.toString();
    }
}

리트코드 답

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;
}

문자열 하나를 가져와서 그걸 기준으로 다른 문자열에서 가지고 있는지 확인한다.

예를 들어 flower, flow, flight면 flower가 flow, flight 중에 있는지 확인한다.

없으면 flower에서 마지막 글자 한 글자를 빼고 다시 비교한다.

예를 들어 flowe가 기준이 되고 확인, 없으므로 다시 한글자 줄여서

flow로 확인

flo로 확인

fl로 확인하고 인덱스가 0이므로 접두어로 fl이 모든 문자열에 있음.

fl을 리턴.

코드도 짧고 굉장히 좋습니다. 무엇보다 제 코드에선 기준점이 될 문자열을 먼저 찾는 작업이 필요한데, 이 코드는 필요가 없어서 좋네요.