LeetCode #14 Longest Common Prefix

nathan·2022년 1월 12일
0

알고리즘문제

목록 보기
101/102

Longest Common Prefix


Link : Longest Common Prefix

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 ""


Ex 1:

  • Input: strs = ["flower","flow","flight"]
  • Output: "fl"

Ex 2:

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

Constraints

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

Java code

class LC5 {
    public String longestCommonPrefix(String[] strs) {
        if (strs.length == 1){
            return strs[0];
        }
        String answer = compareString(strs[0], strs[1]);
        if (strs.length == 2){
            return answer;
        }
        for(int i = 2; i<strs.length; i++){
            answer = compareString(answer, strs[i]);
        }
        return answer;
    }

    static String compareString(String str1, String str2){
        String[] tmpList = lengthCompare(str1, str2);
        String maxStr = tmpList[0];
        String minStr = tmpList[1];
        StringBuilder answer = new StringBuilder();
        for(int i = 0; i < minStr.length(); i++){
            if (maxStr.charAt(i) != minStr.charAt(i)){
                break;
            }
            answer.append(minStr.charAt(i));
        }
        return String.valueOf(answer);
    }

    static String[] lengthCompare(String str1, String str2){
        String[] strList = new String[2]; // strList = [maxStr, minStr]
        int str1Length = str1.length();
        int str2Length = str2.length();
        String maxStr = "";
        String minStr = "";

        if (str1Length > str2Length){
            strList[0] = str1;
            strList[1] = str2;
            return strList;
        }

        strList[0] = str2;
        strList[1] = str1;
        return strList;

    }
}

풀이

static String[] lengthCompare(String str1, String str2)

  • 문자열의 길이를 비교하는 메서드
  • String[] 배열에 첫번째 원소로 긴 문자열을 넣고, 두번째 원소로 짧은 문자열을 넣어 반환한다.

static String CompareString(String str1, String str2)

  • 문자열을 짧은 문자열 길이만큼 반복문을 돌려 prefix를 찾아내는 메서드
  • 문자열로 된 prefix(answer)를 반환한다.

public String longestCommonPrefix(String[] strs)

  • 문자열이 하나만 있을 때, 해당 문자열을 그대로 반환.
  • 문자열이 두개만 있을 때, CompareString 메서드를 통해 구한 prefix를 반환.
  • 문자열이 3개 이상일 때, 처음에 구했던 prefix와 3번째 문자열부터 모든 문자열들을 CompareString 메서드의 인수로 넣어 prefix를 업데이트 한뒤 반환.

교훈

  • 이번에도 문제를 제대로 읽지 않아서, prefix가 아닌 LCS를 구하는 문제로 착각했다..
  • 시간은 엄청 날렸으나, 그래도 다시 읽고 잘못 이해한 부분이 있었음을 깨달았다.
  • 머리가 좋으면 몸이 덜 고생한다.

profile
나는 날마다 모든 면에서 점점 더 나아지고 있다.

0개의 댓글