Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit series activities – click on the task to see the details of the activities.

One, foreword

👨🎓 Author: Bug Bacteria

✏️ blog: CSDN, Nuggets, etc

💌 public account: Magic House of the Circle of the Apes

🚫 special statement: original is not easy, reprint please attach the original source link and this article statement, thank you for your cooperation.

🙏 Copyright notice: part of the text or pictures in the article may come from the Internet or Baidu Encyclopedia, if there is infringement, please contact bug bacteria processing.

Hello, little friends, I am bug bacteria 👀. Gold three silver four, brush the month again. So whether you’re looking for a career change or a career change, get your act together and do the right thing 👣. So, quickly follow the pace of bug bacteria roll up ⏰, become strong from this moment ➕🧈.

In the process of reviewing articles, if you think the articles are helpful to you at all, please don’t be too mean with your likes and bravely light up the articles 👍. Your likes (collect ⭐️+ pay attention to 👨 port + message board) are the best encouragement and support for bugs on my creation path. Time does not abandon 🏃🏻♀️, nuggets stop 💕, cheer up 🏻

Ii. Title Description:

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 1:

STRS = ["flower","flow","flight"]Copy the code

Example 2:

Input: STRS = ["dog","racecar","car"] Output: "" Explanation: The input does not have a common prefix.Copy the code

Tip:

  • 1 <= strs.length <= 200
  • 0 <= strs[i].length <= 200
  • strs[i]Contains only lowercase English letters

Title: LeetCode website

Difficulty: ⭐ ⭐

Iii. Analysis of Ideas:

Transverse scanning method:

The easiest thing to think of is to use violence to solve the problem. The problem is to find the longest common prefix for all elements, which means that each element has such an intersection.

This is done by iterating through each element in the collection, defining a public prefix STR, finding its intersection with the public prefix STR, assigning the intersection to the public prefix STR, and so on. The final public prefix STR is the answer the algorithm wants.

Longitudinal scanning method:

Reverse the idea of violent lateral scanning.

Here’s how to do it: All vertical elements, each element separately put a line, and then in turn back once upon a time traverse all string elements of each column, and then separately for each column character comparison, if all the same, then the next column, if not identical, shows the current column is no longer belong to the public the prefix, to sum up the column before the prefix for the longest part of the public.

Iv. Algorithm implementation:

Horizontal scanning method _AC code:

The specific algorithm code is as follows:

Class Solution {public String longestCommonPrefix(String[] STRS) {if (strs.length == 0) {return ""; } // initialize String ans = STRS [0]; for (int i = 1; i < strs.length; i++) { ans = returnCommStr(ans, strs[i]); } return ans; } public String comStr (String str1, String str2) {// Public prefix comStr = ""; for (int i = 0; i < str1.length(); I ++) {// if I < str2.length(), I < str2.length(); If ((I < str2.length() &&str1.charat (0)! = str2.charAt(0)) || (i < str2.length() && str1.charAt(i) ! = str2.charAt(i))) { return comStr; } // If the same is the same, directly join. if (i < str2.length() && str1.charAt(i) == str2.charAt(i)) { comStr = comStr + str1.charAt(i); continue; } } return comStr; }}Copy the code

Horizontal scanning method _AC code:

The specific algorithm code is as follows:

Class Solution {public String longestCommonPrefix (String [] STRS) {/ / return if directly (STRS = = null | | STRS. Length = = 0) { return ""; } int length = strs[0].length(); Int count = strs.length; For (int I = 0; i < length; Char c = STRS [0]. CharAt (I); char c = STRS [0]. // Match the remaining elements individually with the corresponding i-bit characters. for (int j = 1; j < count; J ++) {// The length reaches STRS [j] length or characters are not equal. They all go straight back. if (i == strs[j].length() || strs[j].charAt(i) ! = c) { return strs[0].substring(0, i); }}} // The first element is the longest prefix. return strs[0]; }}Copy the code

V. Summary:

1. Screenshots of leetcode submission results of horizontal scanning method are as follows:

Lateral scanning **** complexity analysis:

  • Time complexity: O(MN). Where m is the average length of strings in the string array and n is the number of strings. In the worst case, each character of each string in the string array is compared once.
  • Space complexity: O(1). The extra space complexity used is constant.

2. Screenshots of the running results submitted by leetcode of longitudinal scanning method are as follows:

Longitudinal scanning complexity analysis:

  • Time complexity: O(MN). Where mm is the average length of strings in the string array and n is the number of strings. In the worst case, each character of each string in the string array is compared once.
  • Space complexity: O(1). The extra space complexity used is constant.

. .

To sum up, it is obvious that vertical search is superior to horizontal search, both in execution time and memory consumption. The main reason is that there is no for loop, which can compare all the corresponding elements of the string and return them as long as they are not equal. This one is relatively easy.

Furthermore, there are thousands of ways to solve the problem. If you have any better ideas or ideas, please let me know in the comment section. We can learn from each other and grow faster.

Well, that’s all for this episode and I’ll see you next time.

Six, the previous recommendation:

  • Leetcode -1. Sum of two numbers
  • Leetcode – 9. Palindrome
  • Leetcode -13. Roman numeral to integer

. .

Vii. Finally:

If you want to learn more, check out bug Bug’s daily Question LeetCode! Take you to brush together. One person may feel very tired and difficult to persist in brushing, but a group of people will think it is a meaningful thing to brush, urge and encourage each other, and become stronger together.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

☘️ Be who you want to be, there is no time limit, you can start whenever you want,

🍀 You can change from now on, you can also stay the same, this thing, there are no rules to speak of, you can live the most wonderful yourself.

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

​

💌 If this article is helpful to you, please leave a like! (# ^. ^ #);

💝 if you like the article shared by bug fungus, please give bug fungus a point of concern! The danjun ‘ᴗ, you guys will have a cameo appearance with you.

💗 if you have any questions about the article, please also leave a message at the end of the article or add a group [QQ communication group :708072830];

💞 In view of the limited personal experience, all views and technical research points, if you have any objection, please directly reply to participate in the discussion (do not post offensive comments, thank you);

💕 copyright notice: original is not easy, reprint please attach the original source link and this article statement, all rights reserved, piracy will investigate!! thank you