I tried LeetCode every day 14.Longest Common Prefix (Python, Go)
Introduction
@Ishishow is running a free English word site E-tan.
I would like to work on letcode every day to improve my ability as a programmer and give my own way of solving it.
What is Leetcode
leetcode.com This is the practice of coding interviews for software developers. A total of more than 1,500 coding questions have been posted, and it seems that the same questions are often asked in actual interviews.
Introduction to Go language + algorithm I will solve it with Golang and Python to strengthen my brain. (Python is weak but experienced)
5th question (problem 14)
14.Longest Common Prefix
--Problem content (Japanese translation)
Write a function that finds the longest common prefix string in an array of strings.
If there is no common prefix, it returns 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.
Way of thinking
- Extract the shortest word from the array
- Loop through the word character by character
- Check all the characters that appear in the loop and return if they are different, and proceed if they are not different.
Explanation
- You can use the min method to get the element with the fewest characters in the array.
- It can be a for statement or anything.
- return uses slices. You can cut within the specified range with array [: number].
--Answer code
def longestCommonPrefix(self, strs):
"""
:type strs: List[str]
:rtype: str
"""
if not strs:
return ""
shortest = min(strs,key=len)
for i, ch in enumerate(shortest):
for other in strs:
if other[i] != ch:
return shortest[:i]
return shortest
--I'll write it in Go too!
func longestCommonPrefix(strs []string) string {
if len(strs) == 0 {
return ""
}
max := len(strs[0])
for i := 0; i < max; i++ {
b := strs[0][i]
for _, str := range strs[1:] {
if i == len(str) || b != str[i] {
return strs[0][:i]
}
}
}
return strs[0]
}
Go and Python execution time
From the left, RunTime, Memory, language.
Recommended Posts