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를 구하는 문제로 착각했다..
• 시간은 엄청 날렸으나, 그래도 다시 읽고 잘못 이해한 부분이 있었음을 깨달았다.
• 머리가 좋으면 몸이 덜 고생한다.

---