Longest Common Prefix

Aug 7, 2016



#!/usr/bin/env python
# coding=utf-8
def longestCommonPrefix(strs):
    ret=""
    if len(strs) == 0:
        pass
    elif len(strs) == 1:
        ret = strs[0]
    else:
        ls={}
        head_ls = ls
        s = strs[0]
        minLen = len(s)
        for j in range(len(strs[0])):
            head_ls[s[j]]={}
            head_ls=head_ls[s[j]]
        for k in range(len(strs)):
            if k == 0:
                continue
            pre_len = 0
            head_ls = ls
            for j in range(len(strs[k])):
                if strs[k][j] in head_ls.keys():
                    pre_len += 1
                    head_ls=head_ls[strs[k][j]]
                else:
                    break
            if 0 == pre_len:
                ret=""
                break
            elif minLen >= pre_len:
                minLen = pre_len
                ret = strs[k][0:minLen]
    return ret

longestCommonPrefix(["ab","ab","a"])