Topic describes

Write a function to find the longest public prefix in an array of strings.

Returns the empty string “” if no public prefix exists.

Example 1

STRS = [“flower”,”flow”,”flight”]

Output: “fl”

Example 2

Input: STRS = [“dog”,”racecar”,”car”]

Output: “”

Explanation: The input does not have a common prefix.

Thought analysis

  • The first thing that comes to mind is to take two strings, get the longest common prefix of the two strings, and then compare the last common prefix with the next string, and then compare the longest common prefix, and so on until the comparison is complete or there is no common prefix. This is a horizontal scan

    str[0]  str[1] => prefix
prefix  str[2] => new prefix...Copy the code

  • There is also a longitudinal scan, in which the pointer P increases successively from 0 to compare STRS [0] and STRS [1]…. Whether they are equal to each other to determine the common prefix. It’s a longitudinal scan. When scanning here, no pairwise comparison is required; all strings are compared to STRS [0]

AC code

Transverse scan

// Execution time: 0 ms, beat 100.00% of users in all Go commits
// Memory consumption: 2.3MB, beating 25.31% of all Go commits
func longestCommonPrefix(strs []string) string {
    if strs == nil || len(strs) < 1 {
        return ""
    }

    if len(strs) == 1 {
        return strs[0]
    }

    rst := prefix(strs[0], strs[1])
    for i := 2; i < len(strs); i++ {
        p := prefix(rst, strs[i])
        if len(p) == 0 {
            return p
        }
        rst = p
    }
    return rst
}

// Get the common prefix for both strings
func prefix(str1 string, str2 string) string {
    len1 := len(str1)
    len2 := len(str2)

    var length int
    if len1 < len2 {
        length = len1
    } else {
        length = len2
    }

    for i := 0; i < length; i++ {
        ifstr1[i] ! = str2[i] {return str1[0:i]
        }
    }
    return str1[0:length]
}
Copy the code

Longitudinal scanning

// Execution time: 0 ms, beat 100.00% of users in all Go commits
// Memory consumption: 2.3MB, beating 87.00% of all Go commits
func longestCommonPrefix(strs []string) string {
    if strs == nil || len(strs) < 1 {
        return ""
    }

    for i := 0; i < len(strs[0]); i++ {
        for j := 1; j < len(strs); j++ {
            if len(strs[j])- 1 < i || strs[0][i] ! = strs[j][i] {return strs[0] [0:i]
            }
        }
    }
    return strs[0]}Copy the code

conclusion

  • Some problems, think of relatively simple, but write or a lot of details need to pay attention to.