Leetcode with Golang: Longest Common Prefix

Leetcode problem #14 solution in Golang

source: https://www.freecodecamp.org/news/what-is-go-programming-language/

Motivation

Recently, I decided that I wanted to prep for interviews, coding competitions, and learn a new programming language. To kill all of these birds with one stone, I decided to practice Leetcode problems daily with Golang. Solving algorithm problems in a language you aren’t familiar with forces you to think about the problem that actually needs to be solved, which helps you become a better developer. Of course, there are the initial hiccups with getting the correct syntax, but the most important thing is being able to solve problems regardless of tooling.

Soon after this journey began, I noticed that there isn’t nearly as much support for Leetcode problems in Golang as there is C++, Python, or Java. Given the history of those languages, its not surprising that a modern language like Go doesn’t have the same level of support. However, this article will be the first in a series of posts where I provide solutions to Leetcode problems in Golang.

DISCLAIMER: As mentioned before, I am still learning Go. If anyone has any recommendations to make my code more idiomatic, please provide in the comments.

Longest Common Prefix

Difficulty: Easy

Pass Rate: 38.8%

Naive Approach

We are given a slice of strings and told to find the most common prefix. There are a couple of basic tasks that will need to be performed. We will need to iterate through the slice and compare individual characters of the strings in the slice. When comparing the characters in the slice, we will need to check if they are equal or not. If so, we will keep track of the characters that are common and return the longest one. It is also important to note that most common prefix means that all entries must have this prefix.

The naive/brute force approach would be to iterate through the slice and individual characters to perform the required tasks. Though this would be correct, it would yield a suboptimal O(n²) solution. However, now that we have this frame of the problem, we can optimize our approach.

Optimized Solution

There are various strategies that can be used to solve this problem, such as divide and conquer along with various sorting and searching methods. The divide and conquer would allow us to use a recursive approach to the problem, while sorting and searching methods would allow us to reduce the amount of comparisons needed to take place. Both approaches allow us to reduce our problem size from O(n²) to a more efficient solution.

We will go with using a sorting method to sort the slice of strings lexicographically. Though divide and conquer approaches generally provide beautiful and simple solutions, the logic used to implement a solution that utilizes sorting to find the longest common prefix is fascinating and beautiful in its own right. Utilizing sorting, we are able to find a solution for the entire slice, no matter the size, looking at only two elements in the array: the first and last elements.

Once the slice is sorted, we are able to take the first and last entries in the slice and compare only those two to determine the longest common prefix. The way this logic works is that if the first element in the first and last entries of the slice are equal after the array has been sorted, then that and the remaining elements that are equal form the longest common prefix. Once a character between the first and last slice entries do not equal, then the longest common prefix has been found. This logic also solves cases for when there is no common prefix; if the first characters of the first and last slice entries aren’t equal, then there is simply no common prefix.

Here is the solution in Golang:

func longestCommonPrefix(strs []string) string {
    var longestPrefix string = ""
    var endPrefix = false
    
    if len(strs) > 0 {
        sort.Strings(strs)
        first := string(strs[0])
        last := string(strs[len(strs)-1])
        
        for i := 0; i < len(first); i++ {
            if !endPrefix && string(last[i]) == string(first[i]) {
                longestPrefix += string(last[i])
            } else {
                endPrefix = true
            }
        }
    }
    return longestPrefix
}

Disclaimer: Utilizing a divide and conquer approach typically produces an O(nlogn) solution, where as utilizing sort in Golang is O(nlogn) in addition to comparing the characters in the first and last two indexes of the slice which is O(n) worst case. So in terms of runtime, this solution is still optimized to O(n), but a divide and conquer approach may provide an even more powerful optimization

Closing Remarks

Here are the performance metrics for our solution:

Please provide any feedback in the comments!