[LeetCode] 14. Longest Common Prefix #Easy #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 "".

예제 1

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

예제 2

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 lowercase English letters if it is non-empty.

문제풀이

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 1. 변수 선언 및 초기화
        String result = "";
        int shortestLength = 200;
        StringBuilder sb = new StringBuilder();

        // 2. 배열 요소 중 문자열 최소 길이 추출
        for (String str : strs) {
            int newStrLength = str.length();
            if (str.length() < shortestLength) shortestLength = newStrLength;
        }

        // 3. 가장 짧은 문자열 만큼 prefix 판별 
        for (int i=0; i<shortestLength; i++) {
            // 플래그 및 문자 초기화
            boolean prefixFlag = true;
            char c = strs[0].charAt(i);

            // 문자열 배열 순회하며 동일 여부 확인
            for (int j=0; j<strs.length; j++) {
                if (c != strs[j].charAt(i)) prefixFlag = false;
            }

            // 플래그가 거짓이라면 순회 탈출
            if (!prefixFlag) break;

            // 플래그가 참이라면 결과에 추가
            sb.append(c);
        }

        // 4. 반환
        result = sb.toString();
        return "".equals(result) ? "" : result;
    }
}

• 문자열 배열에서 각 문자열의 길이가 모두 다를 것이다.
• 널 포인터 예외를 피하고 싶다면 문자열의 최소 길이를 구해서 그만큼만 반복을 돌려야 한다.
• 그 외에는 특별한 건 없다. 

 

마치며

이중 for문을 없애고 싶어서 ChatGPT에 물어봤는데, 신박한 아이디어가 있었다. 

 

ChatGPT 코드

import java.util.Arrays;

public class LongestCommonPrefix {
    public static String longestCommonPrefix(String[] strs) {
        // 입력 배열이 null이거나 비어있으면 빈 문자열 반환
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 문자열 배열을 사전순으로 정렬합니다.
        Arrays.sort(strs);

        // 정렬 후 첫 번째 문자열과 마지막 문자열만 비교하면 됩니다.
        String first = strs[0];
        String last = strs[strs.length - 1];

        int i = 0;
        // 첫 번째와 마지막 문자열을 하나씩 비교하면서 공통 접두사의 길이를 찾습니다.
        while (i < first.length() && i < last.length() && first.charAt(i) == last.charAt(i)) {
            i++;
        }

        // 첫 번째 문자열의 처음 i개의 문자가 가장 긴 공통 접두사가 됩니다.
        return first.substring(0, i);
    }

    public static void main(String[] args) {
        String[] input = {"flower", "flow", "flight"};
        System.out.println("공통 접두사: " + longestCommonPrefix(input));  // 출력: "fl"
    }
}

• 문자열 배열을 사전순으로 정렬하고 첫 번째 문자열과 마지막 문자열만 확인하는 것이다.

이런 아이디어는 어떻게 떠올리는 걸까. 🤔 

 

이미지 출처

[김은우의 에듀테크 트렌드 따라잡기] 코딩 교육 사이트 LeetCode가 보여주는 코딩교육의 핵심