Shulou(Shulou.com)05/31 Report--

This article introduces the knowledge of "how to achieve the longest common prefix on C++". In the operation of practical cases, many people will encounter such a dilemma. Then let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Longest Common Prefix longest common prefix

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: ["flower", "flow", "flight"]

Output: "fl"

Example 2:

Input: ["dog", "racecar", "car"]

Output: ""

Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a Murz.

This question allows us to find a common prefix for a series of strings, without any special skill, without brain search, defining two variables I and j, where I is traversing the characters in the search string and j is traversing each string in the string set. If the words are arranged up and down here, it is equivalent to a two-dimensional array in which the length of each row may not be equal. The traversal order is different from the general horizontal row-by-row traversal, but it uses vertical column-by-column traversal. In the process of traversal, if a line is gone, it means that it is the shortest word. Because the length of the common prefix cannot be longer than the shortest word, the common prefix that has been found is returned at this time. Take a word from a certain position in the first string each time, and then traverse the corresponding positions of all other strings to see if they are equal. If any are not satisfied, return res directly. If all are the same, store the current character in the result and continue to check the characters in the next position. See the code as follows:

C++ solution one:

Class Solution {public: string longestCommonPrefix (vector& strs) {if (strs.empty ()) return ""; string res = ""; for (int j = 0; j)

< strs[0].size(); ++j) { char c = strs[0][j]; for (int i = 1; i < strs.size(); ++i) { if (j >

= strs [I] .size () | | strs [I] [j]! = c) {return res;}} res.push_back (c);} return res;}}

Java solution 1:

Public class Solution {public String longestCommonPrefix (String [] strs) {if (strs = = null | | strs.length = = 0) return ""; String res = new String (); for (int j = 0; j)

< strs[0].length(); ++j) { char c = strs[0].charAt(j); for (int i = 1; i < strs.length; ++i) { if (j >

= return res; [I] .length () | | strs [I] .charat (j)! = c) {return res;}} res + = Character.toString (c);} return res;}}

We can simplify the above method appropriately. If we find that the characters in the corresponding position of the current character and the first string are not equal, it means that there will be no longer common prefix. We can directly extract the substring of the common prefix by using the substr method. If no result is returned before the end of the traversal, the first word is a common prefix and can be returned as a result. The code is as follows:

C++ solution 2:

Class Solution {public: string longestCommonPrefix (vector& strs) {if (strs.empty ()) return ""; for (int j = 0; j

< strs[0].size(); ++j) { for (int i = 0; i < strs.size(); ++i) { if (j >

= return [I] .size () | | strs [I] [j]! = strs [0] [j]) {strs [I] .substr (0, j);} return strs [0];}}

Java solution II:

Class Solution {public String longestCommonPrefix (String [] strs) {if (strs = = null | | strs.length = = 0) return ""; for (int j = 0; j)

< strs[0].length(); ++j) { for (int i = 0; i < strs.length; ++i) { if (j >

= strs[ I] .length () | | strs[ I] .charat (j)! = strs [0] .charat (j)) {return strs.substring (0, j);} return strs [0];}}

Let's take a look at another solution, which sorts an array of input strings, and think about the benefits of doing so. Since it is sorted alphabetically, two strings with more common letters will be arranged together, and strings with fewer letters will be squeezed to both ends, so if there is a common prefix, it must appear in the string at both ends, so you only need to find the common prefix of the first and last letter strings. For example, example 1 is sorted to ["flight", "flow", "flower"], and example 2 is sorted to ["cat", "dog", "racecar"]. Although example 2 does not have a common prefix, it can be considered as an empty string and appears in the string at both ends of the string. Because it is arranged in alphabetical order, not by length, the relationship between the length of the first and last letters is unknown. To prevent overflow errors, only traverse the length of the shorter one and find out the common prefix to return. See the code as follows:

C++ solution 3:

Class Solution {public: string longestCommonPrefix (vector& strs) {if (strs.empty () return ""; sort (strs.begin (), strs.end ()); int I = 0, len = min (strs [0] .size (), strs.back (). Size ()); while (I < len & & strs [0] [I] = strs.back () [I]) + + i; return strs [0] .substr (0, I) }}

Java solution 3:

Class Solution {public String longestCommonPrefix (String [] strs) {if (strs = = null | | strs.length = = 0) return "; Arrays.sort (strs); int I = 0, len = Math.min (strs [0] .length (), strs [strs.length-1] .length ()); while (I < len & & strs [0] .charat (I) = strs [strs.length-1] .charat (I)) Return strs [0] .substring (0, I);}} "how to achieve the longest common prefix in C++" ends here. Thank you for reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.