[Java] 14. Longest Common Prefix

난이도: EASY

문제

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

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

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

---

 

시도 1

class Solution {
    public String longestCommonPrefix(String[] strs) {
        StringBuilder sb = new StringBuilder();
        
        // 모든 문자열 중 가장 짧은 길이 찾기
        int minLen = Integer.MAX_VALUE;
        for (String str : strs) {
            minLen = Math.min(minLen, str.length());
        }

        for(int i = 0; i < minLen; i++) {
            boolean same = false;
            char current = strs[0].charAt(i);

            if (current == strs[1].charAt(i) && current == strs[2].charAt(i)) {
                same = true;
                sb.append(strs[0].charAt(i));              
            }

            if(!same) {
               if(sb.length() == 0) return "";
            }
        }
        return sb.toString();
    }
}

run 할 때는 아무문제가 없어서 몰랐는데, submit 해보니 아래와 같은 오류가 나서 문제 설명과 조건 찬찬히 다시 읽어봄.

java.lang.ArrayIndexOutOfBoundsException: Index 1 out of bounds for length 1 at line 15, Solution.longestCommonPrefix at line 56, __DriverSolution__.__helper__ at line 86, __Driver__.main

 

1 <= strs.length <= 200 이 부분이 내가 간과했던 부분. 무조건 3개의 단어가 나온다는 조건하에 풀어서 바운드익셉션이 난 것.

이중for문안쓰려고 저렇게했던건데 바보같은 짓이었다 ㅎㅎ...!

 

시도2

class Solution {
    public String longestCommonPrefix(String[] strs) {
        StringBuilder sb = new StringBuilder();
        
        // 모든 문자열 중 가장 짧은 길이 찾기
        int minLen = Integer.MAX_VALUE;
        for (String str : strs) {
            minLen = Math.min(minLen, str.length());
        }

        // 한 개의 단어만 있는 경우, 그대로 반환
        if(strs.length == 1) return strs[0];

        // 단어 중 가장 짧은 단어만큼 반복
        for(int i = 0; i < minLen; i++) {
            boolean same = false;
            char current = strs[0].charAt(i);

            for(int x = 1; x < strs.length; x++) {
                if (current != strs[x].charAt(i)) {                    
                    same = false;
                    break;
                } else {
                    same = true;
                }               
            }

            if(same) {
                sb.append(strs[0].charAt(i));              
            } else if(sb.length() == 0) return "";

        }
        return sb.toString();
    }
}

 

 

아하..... 붙은거끼리만 연산해야하는데 떨어진것끼리도 체크되서 문제가 생겼다.

공통 접두사가 끊기면 즉시 종료하게 바꿔줬다.

 

---

 

나의 최종 제출 답안:

class Solution {
    public String longestCommonPrefix(String[] strs) {
        StringBuilder sb = new StringBuilder();
        
        // 모든 문자열 중 가장 짧은 길이 찾기
        int minLen = Integer.MAX_VALUE;
        for (String str : strs) {
            minLen = Math.min(minLen, str.length());
        }

        // 한 개의 단어만 있는 경우, 그대로 반환
        if(strs.length == 1) return strs[0];

        // 단어 중 가장 짧은 단어만큼 반복
        for(int i = 0; i < minLen; i++) {
            boolean same = false;
            char current = strs[0].charAt(i);

            for(int x = 1; x < strs.length; x++) {
                if (current != strs[x].charAt(i)) {                    
                    same = false;
                    // 공통 접두사가 끊기면 즉시 종료
                    if (!same) return sb.toString();
                } else {
                    same = true;
                }               
            }            
            if(same) sb.append(strs[0].charAt(i));              
        }
        return sb.toString();
    }
}

 

---

 

chatGPT에게 더 간단하고 효율적이게 수정해달라고 요청한 답안:

 

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 모든 문자열 중 가장 짧은 길이 찾기
        int minLen = Integer.MAX_VALUE;
        for (String str : strs) {
            minLen = Math.min(minLen, str.length());
        }

        // 한 개의 단어만 있는 경우, 그대로 반환
        if (strs.length == 1) return strs[0];

        StringBuilder sb = new StringBuilder();

        // 단어 중 가장 짧은 단어만큼 반복
        for (int i = 0; i < minLen; i++) {
            char current = strs[0].charAt(i);

            for (int x = 1; x < strs.length; x++) {
                if (current != strs[x].charAt(i)) {                    
                    return sb.toString();  // 🚀 공통 접두사가 끊기면 즉시 반환
                }
            }

            sb.append(current);  // ✅ 모든 단어에서 공통된 문자를 추가
        }

        return sb.toString();
    }
}

 

맞네..... 처음에 푼 방식에서 수정하다보니 이런걸 체크를 못했군 ㅎㅎ....

아직도 지난회사에서 혼돈지옥의 자스소스 유지보수 할 때 얼레벌레 수정하던 방식을 못버리고....