跳转至

14. 最长公共前缀

题目

# 14. 最长公共前缀
# 编写一个函数来查找字符串数组中的最长公共前缀。

# 如果不存在公共前缀,返回空字符串 ""。

# 示例 1:

# 输入: ["flower","flow","flight"]
# 输出: "fl"
# 示例 2:

# 输入: ["dog","racecar","car"]
# 输出: ""
# 解释: 输入不存在公共前缀。
# 说明:

# 所有输入只包含小写字母 a-z 。

解答

class Solution:
    def longestCommonPrefix(self, strs):
        if strs == []: return ''
        if strs[0] == '': return ''

        ret = strs[0]
        for word in strs[1:]:
            if word == '': return ''
            ret, _len = self.two_word_common_prefix(word, ret)
            if ret == '': return ret
        return ret


    def two_word_common_prefix(self, word1, word2):
        '''
                f l o w e r
              f 1   
              l   1
              o     1
              w       1
              return max_common_prefix, len(max_common_prefix)
        '''
        word1 = list(word1)
        word2 = list(word2)

        row = [None] * len(word1)
        arr = [row] * len(word2)

        i = 0
        min_len = min(len(word1), len(word2))
        while i < min_len:
            if word1[i] == word2[i]:
                arr[i][i] = 1
            i += 1

        tmp_common_prefix, max_common_prefix, max_len = '', '', 0

        for i in range(min_len):
            if arr[i][i] == 1:
                if tmp_common_prefix == '' or arr[i][i] == arr[i-1][i-1]:
                    tmp_common_prefix += word1[i]
            else:
                break

        max_len = max(len(max_common_prefix), len(tmp_common_prefix))
        max_common_prefix = max_common_prefix if len(max_common_prefix) == max_len else tmp_common_prefix
        return max_common_prefix, max_len


def test_two_word_common_prefix():
    b = Solution()
    assert(b.two_word_common_prefix("flower", "flow") == ('flow', 4))
    assert(b.two_word_common_prefix("flower", "flight") == ('fl', 2))
    assert(b.two_word_common_prefix("flow", "flight") == ('fl', 2))

    assert(b.two_word_common_prefix("dog", "racecar") == ('', 0))
    assert(b.two_word_common_prefix("car", "racecar") == ('', 0))
    assert(b.two_word_common_prefix("car", "dog") == ('', 0))

def test_longest_common_prefix():
    b = Solution()
    assert(b.longestCommonPrefix(["flower","flow","flight"]) == 'fl')
    assert(b.longestCommonPrefix(["dog","racecar","car"]) == '')

class Solution:
    def longestCommonPrefix(self, strs):
        if not strs: return ''
        if strs[0] == '': return ''

        c = strs[0]
        pre = ''

        i = 0
        while True:
            if i >= len(c): return pre
            for s in strs[1:]:
                if i >= len(s): return pre
                if s[i] != c[i]: return pre
            else:
                pre += c[i]
            i += 1
        return pre