[leetcode] 14. Longest Common Prefix

 

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

 

개인적으로, 구현이 어려웠던 문제였다. 왜냐면 인덱스 조정하기가 까다로워서.

아이디어는 굉장히 간단하다.

주어진 리스트의 첫번째 문자열을 기준으로 진행한다.

리스트로 주어진 모든 문자열을 순회하면서 같은 인덱스 위치의 값이 같은지 확인한다.

같지 않은 값을 발견하면, 앞에서부터 해당 인덱스까지의 부분 문자열을 잘라서 반환한다.

모두 같다면 첫번째 문자열을 반환한다.

첫번째 문자열보다 길이가 짧은 문자열이 나오면, 즉시 앞에서부터 인덱스까지의 부분 문자열을 잘라서 반환한다.

 

 

class Solution:
    def longestCommonPrefix(self, strs: List[str]) -> str:
        if strs is None or len(strs) <= 0 : return ""
        if len(strs) == 1 : return strs[0]

        i=0
        for a in strs[0]:
            for s in strs:
                if (len(s) <= i or not s[i]==a):
                    return strs[0][0:i]
            i+=1
        return strs[0]

 

 

혹은, 첫번째 문자열을 기준으로, 다음 문자열들을 하나씩 비교해가며 공통된 부분만 남긴다.

 

class Solution:
    def check(self, str1, str2) -> int:
        if (len(str1)<len(str2)) : limit = len(str1)
        else : limit = len(str2)

        i = 0
        for i in range(0, limit):
            if(str1[i] != str2[i]): return i

        return i+1

    def longestCommonPrefix(self, strs: list[str]) -> str:
        str = strs[0]

        for i in range(1, len(strs)):
            next_str = strs[i]
            if(len(next_str)==0): return ""
            x = self.check(str, next_str)
            str = str[:x]

        return str

 

 

---

 

 

< English (feedback by ChatGPT) >

 

Personally, It was hard to implement because it was tricky to controll index.

(Personally, this was a hard problem to implement because controlling the index was tricky.)

 

The Idea is simple.

(The idea itself is simple.)

 

It goes with the first string in the given list.

(We start with the first string in the given list as a reference.)

 

Iteratre through the all string in the given list and check whether or not that the values at the index are the same.

(Then, we iterate through all the strings in the list and check whether the characters at each index are the same.)

 

If finds not the same value, return the substring from the first to the index of the string.

(If we find a mismatch, we return the substring from the beginning up to that index.)

 

If all the same, return the first string.

(If all characters match across the strings, we return the first string.)

 

If finds a string which the length is shorter than the first string, then retrun the substring from the first to the index of the string right away.

(Also, if we encounter a string that is shorter than the first one, we immediately return the substring from the beginning up to that index.)

 

 

 

tip:

- as a reference : You are using something as a standard or basis to compare or guide your actions.

- up to : until a certain point, NOT INCLUDING that point
for ex, "Return the substring from the beginning up to that index."

This means: Return everything before that index, not including the character at that index.