# [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

### 【 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
https://blog.csdn.net/D16100?spm=1000.2115.3001.5343&type=blog
Welcome to exchange and study

# subject ：

author ： Power button (LeetCode)
source ： Power button （LeetCode）

## 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;
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