This is the 8th day of my participation in the First Challenge 2022

First, write first

I heard you’re still writing a two-layer for loop to solve the sum of two numbers?

LeetCode 2: Sum of two numbers transfer gate: the median of two sorted arrays, “most” technical solution!

LeetCode 第 3 题 : Longest loop transport gate: Horse-and-cart algorithm to solve longest loop! Manacher

LeetCode 4 题 conversion of string to integer (ATOI) : Solve ATOI with “foolish old man removing mountains” method, think clever!

Question 5: Longest public prefix, for interview, looking forward to your participation.

Today’s topic

Write a function to find the longest public prefix in an array of strings. Returns the empty string “” if no public prefix exists.

Example:

The sample1: Input: ["flower"."flow"."flight"] output:"fl"The sample2: Input: ["dog"."racecar"."car"] output:""Explanation: The input does not have a common prefix.Copy the code

Note: All inputs contain only lowercase letters A-Z.

Three, the analysis

This topic, at first glance, whether the topic is dry or examples are – how so simple? The illusion, indeed, looks simple, but there are still many difficulties, for example: the length of STRS is variable; The length of string in STRS is also variable, generally speaking, it is relatively simple, I saw the topic of the first idea is brute force search, comparison, this method is not very good, optimize the idea, the main flow is as follows:

Fourth, the problem solving

  • My approach:

Double for loop time: less than O(n^2)

Write a function to find the longest public prefix in an array of strings. Returns the empty string "" if no public prefix exists. Longest Common Prefix '''


class Solution:
	def longestCommonPrefix(self, strs) :
		""" :type strs: List[str] :rtype: str """
		len0 = len(strs)
		if len0 == 0:
			return ' '
		list_len = []
		Find the shortest string length
		for i in range(len0):
			list_len.append(len(strs[i]))
		list_len.sort()
		Fetch the shortest substring
		I'm just going to take min_len of the first substring
		com_str = strs[0] [0:list_len[0]]
		b0 = com_str
		for s in strs:
			for i in range(list_len[0) :ifs[i] ! = com_str[i]:# Judge to be unequal
					a0 = s[0:i]
					if len(b0) >= len(a0):  # is the last longest public prefix longer than it is now
						b0 = a0
		return b0
Copy the code

Submit the results

Test data: 118 groups running time: 48ms beat percentage :92.21%

  • Daniel method:

Layer 1 for loop time complexity: O(n)

# Daniel's method, 9 lines of code
class Solution:
	def longestCommonPrefix(self, strs) :
		""" :type strs: List[str] :rtype: str """
		res = ""
		if len(strs) == 0:
			return ""
		The # zip() function takes an iterable as an argument, packs the corresponding elements of the object into tuples, and returns a list of those tuples
		for each in zip(*strs):
			# Create an unordered non-repeating set of elements using a collection
			if len(set(each)) == 1:
				res += each[0]
			else:
				return res
		return res
Copy the code
  • Submit the results

Test data: 118 groups running time: 28ms beat percentage :95.84%

Five, the conclusion

Today, a reader asked me why I am so good, and I replied, “I am just like everyone else.” What makes me good is my persistence. That’s what learning is about.

  • 1. I have to keep learning and find the right direction. I have to learn Python without thinking about Java.
  • 2. Pay for knowledge and spend money on lessons that will be useful to you (technical, emotional, life, etc.)

I hope that you will learn something from me. In terms of technology or life, you can make progress through more communication. Persistence and hard work: results.