14. Longest Common Prefix

Problem

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] consists of only lower-case English letters.

Problem Summary

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

If there is no common prefix, return an empty string "".

Solution Ideas

• Sort strs in ascending order by string length, and find the length minLen of the shortest string in strs
• Compare the characters in the shortest string with those in the other strings one by one. If they are not equal, return commonPrefix; otherwise, add the character to commonPrefix

Code

package leetcode

func longestCommonPrefix(strs []string) string {
	prefix := strs[0]

	for i := 1; i < len(strs); i++ {
		for j := 0; j < len(prefix); j++ {
			if len(strs[i]) <= j || strs[i][j] != prefix[j] {
				prefix = prefix[0:j]
				break
			}
		}
	}

	return prefix
}