[LeetCode] - 14. Common Prefix

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Common Prefix" 문제입니다.

--> https://leetcode.com/problems/longest-common-prefix/description/

 

문제 : 

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.

---

이 문제는 주어진 문자열 배열에서 가장 긴 공통 접두사를 찾는 함수 작성 문제입니다. 공통 접두사가 없으면 빈 문자열을 반환해야 합니다. 예를 들어, 입력이 ["flower","flow","flight"]인 경우 출력은 "fl"이며, ["dog","racecar","car"]인 경우 출력은 ""입니다.

제 코드를 바로 보시겠습니다 : 

class Solution {
    public String longestCommonPrefix(String[] strs) {
        Arrays.sort(strs); // sort the words in alphabetic order
        
        String firstWord = strs[0]; // It's the first word of strs array
        String lastWord = strs[strs.length - 1]; // Last word of the array

        int index = 0; // index that we will need to do a substring later

        while (index < firstWord.length() && index < lastWord.length()) {
            if (firstWord.charAt(index) == lastWord.charAt(index)) {
                index++;
            } else {
                break;
            }
        }   

        return firstWord.substring(0, index);
    }
}

 

이 코드를 설명드리자면 : 

1. 문자열 배열 정렬 :
   • 문자열 배열을 알파벳 순서로 정렬합니다.
2. 첫 번째 단어와 마지막 단어 설정 :
   • 정렬된 배열의 첫 번째 단어와 마지막 단어를 변수에 저장합니다.
3. 공통 접두사 찾기 :
   • 첫 번째 단어와 마지막 단어의 문자를 비교하여 공통 접두사의 길이를 찾습니다.
   • 문자가 같으면 인덱스를 증가시키고, 다르면 반복을 종료합니다.
4. 결과 반환 :
   • 첫 번째 단어의 접두사를 잘라서 반환합니다.

시간 및 공간 복잡도 :

1. 시간 복잡도 :
   • 정렬 시간: O(n log n), 여기서 n은 문자열 배열의 길이입니다.
   • 첫 번째 단어와 마지막 단어를 비교하는 데 드는 시간: O(m), 여기서 m은 첫 번째 단어와 마지막 단어의 길이입니다.
   • 전체 시간 복잡도는 O(n log n + m)입니다.
2. 공간 복잡도:
   • 문자열 배열을 정렬하는 데 추가적인 공간이 필요할 수 있지만, 주로 정렬 알고리즘에 따라 다릅니다. 대부분의 경우 O(log n)의 추가 공간을 사용합니다.
   • 공통 접두사를 저장하기 위해 O(1)의 공간을 사용합니다.
   • 따라서 전체 공간 복잡도는 O(log n)입니다.

---

더 빠른 코드가 있었습니다 다른 사람의 코드입니다만, 공유해 드리겠습니다 : 

public class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) return "";
        String prefix = strs[0];
        for (String s : strs)
            while (s.indexOf(prefix) != 0)
                prefix = prefix.substring(0, prefix.length() - 1);
        return prefix;
    }
}
// ayeshakalsoom06 유저의 코드

 

이 분도 저랑 비슷한 아이디어지만 while문의 조건이 더 탁월합니다.

---

내 코드와 다른 유저의 코드 Runtime 결과