My first by-my-self AC solution(Python, 60ms)


  • 0
    W

    Use two sub-arrays to compare with each other. Although the waste on time is O(n^2), it is fast enough to AC:

    class Solution:
    # @param {string[]} strs
    # @return {string}
    def longestCommonPrefix(self, strs):
        if not strs:
            return ''
            
        lcp_len = len(strs[0])
        lcp0 = strs[0]
        lcp1 = ''
        
        for i in xrange(1, len(strs)):
            lcp_len = min(lcp_len, len(strs[i]))
            for j in xrange(lcp_len):
                if lcp0[j] == strs[i][j]:
                    lcp1 += strs[i][j]
                else:
                    break
            
            lcp0 = lcp1
            lcp1 = ''
            lcp_len = len(lcp0)
        
        return lcp0
    

    First AC solution by myself, comments and suggestions please!


  • 0
    L

    didn't look at details of code, but just one comment: u don't need to compare the whole substring, just comparing the the new char to be added is okay.


  • 0
    W

    Thank you! But what's mean? Could u explain it more particularly?


  • 0
    L

    for j in xrange(lcp_len):
    if lcp0[j] == strs[i][j]:
    This compare should be simplified to O(1). because in previous iteration we guaranteed the substring to be common prefix of all strings, in the current iteration we only need to compare the chars at current position, if all are equal, add this char to substring and go to next iteration, otherwise stop and return the final substring. Hope will make sense.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.