Make writing a habit together! This is the third day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

I. Problem description

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

Returns the empty string “” if no public prefix exists.

Title link: The longest public prefix.

Two, the title requirements

Sample 1

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

The sample 2

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

inspection

1. Value of the string and prefix 2. It takes 15 to 35 minutesCopy the code

Third, problem analysis

The longest common prefix. In example 1, we’ll use the first string flower as the base.

First of all, the bottom left represents the prefix of the base, the left represents whether any other string contains the prefix 1 contains 0 does not, and the far left represents the longest common prefix by far.

f                      1                    1               1
fl                     1                    1               2
flo                    1                    0               2
flow
flower
Copy the code

When you have a zero, you don’t have to go down. What’s the use of going back if none of the previous characters are included?

Four, coding implementation

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int i,j,n=strs.size(a);// Initialize the data
        string s=strs[0],t,k="";// use the first string as the base,k as the substring prefix and
        for(i=0; i<s.size(a); i++) { t=s.substr(0,i+1);// Iterate backwards, prefix and increment
            for(j=1; j<n; j++)// Iterate over other array elements
            {
                if(strs[j].find(t)! =0)// As long as the prefix does not exist
                    return k;// Direct output bye
            }
            k=t; // Otherwise update the data
        }
        returnk; }};Copy the code

V. Test results