current position:Home>[fun bath] daily practice - "Li Kou: introduction to leetcode algorithm" (c + +): String - "longest common prefix - hypothetical sequential judgment method" 2021-12-16

[fun bath] daily practice - "Li Kou: introduction to leetcode algorithm" (c + +): String - "longest common prefix - hypothetical sequential judgment method" 2021-12-16

2022-01-26 23:37:04 Playful bass

【 Play bass 】 Practice every day ——《 Power button :LeetCode Introduction to algorithm 》(C++): character string ——「 The longest common prefix —— Hypothesis sequential judgment method 」 2021-12-16

Welcome to my WeChat official account. : Programming Pastor
ID:bianchengzhizhen
Timely sharing algorithm 、 Computer science and game programming
I am CSDN Blog home page :
https://blog.csdn.net/D16100?spm=1000.2115.3001.5343&type=blog
Welcome to exchange and study

subject :

author : Power button (LeetCode)
link :https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnmav1/
source : Power button (LeetCode)
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .

Topic 1 : The longest common prefix

Write a function to find the longest common prefix in the string array .
If no common prefix exists , Returns an empty string “”.

Example 1:
Input :strs = [“flower”,“flow”,“flight”]
Output :“fl”

Example 2
Input :strs = [“dog”,“racecar”,“car”]
Output :""
explain : Input does not have a common prefix .

Tips :
1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] It's only made up of lowercase letters

Related labels
character string

C++ Source program :

class Solution {
    
public:
    string longestCommonPrefix(vector<string>& strs) {
    
        //  I don't know why I use length()  Compilation error 
        //  First judge strs When the array does not exist 
        if (strs.size() == 0)
            return "";

        //  Assume that the first string of the array is the public prefix of the second .
        string pre = strs[0];
        int i = 1;  //  At least two arrays , If only one , Then it itself is the longest public prefix , So from 1 Start 
        while(i < strs.size()){
    
            while(strs[i].find(pre) != 0)  //  From the second string of the array ( Subscript to be 1) Start ,find The function looks for the existence of the first ( That is, the previous string ) The characters of . If there is , Will return the address of the first character , Return 0 It means that the first and second have the same common prefix 
                pre = pre.substr(0, pre.size() - 1 );// substr Intercept pre from 0 Subscript to length -1  The number of   character . For example size() = 4,  that substr(0,4-1), That is, intercept the subscript 0 Start length is 3 String , Subscript to be 0,1,2  This string of .
            i++;
        }
        return pre;
    }
};

Personal experience :

Read this question , A key factor must be understood —— That is, the prefix in the longest common prefix , That is, it can only be the prefix composed of the first few characters in each string . Make this point , Then you can know that what you have to consider is not very responsible .
We can directly assume that the first string of the array is the longest common prefix , And find out the longest common prefix between it and the second string . If there isn't the same , So long back “”, non-existent .

Related to knowledge :

  1. str1.find(str2) function
    I.e. find str1 in str2 The first subscript address of the string

I am CSDN Blog has detailed knowledge explanation :
https://blog.csdn.net/D16100/article/details/121978209?spm=1001.2014.3001.5501

  1. str1.substr(a,b) function
    Intercepting string str1 In the from a At the beginning b A string of length

I am CSDN Blog has detailed knowledge explanation :
https://blog.csdn.net/D16100/article/details/121978625

copyright notice
author[Playful bass],Please bring the original link to reprint, thank you.
https://en.cdmana.com/2022/01/202201262337009596.html

Random recommended