leetcode#14 Longest Common Prefix

1. 문제

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

2. 나의 풀이

2.1 이중 For문으로 풀기

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        
        base_word = strs[0]
        #for word in strs:
        #    if len(base_word) > len(word):
        #        base_word = word
        
        # print("base_word", base_word)
        result = ""
        for index, char in enumerate(base_word):
            # print("for", index, char, result)         
            is_included = True
            for word in strs:
                # print("inside for", index, char, result, word)
                try:
                    if word[index] != char :
                        is_included = False
                        break
                except:
                    is_included = False
                    break
                    
            if is_included is False:
                break
            result += char
            # print("="*3)
        
        return result

2.2 divide and conquer

class Solution(object):
    def getPrefix(self, word_a, word_b):
        result = ""
        for i in range(0, len(word_a)):
            
            try:
                if word_a[i] != word_b[i]:
                    return result
            except:
                return result
            
            result += word_a[i]
        return result
        
    
    def divideAndConquer(self, strs):
        if len(strs) > 2:
                left = self.divideAndConquer(strs[:len(strs)//2])
                right = self.divideAndConquer(strs[len(strs)//2:]) 
                return self.getPrefix(left, right)
        if len(strs) == 2:
            return self.getPrefix(strs[0], strs[1])
        return strs[0]
    
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        return self.divideAndConquer(strs)

3. 남의 풀이

Reference