最長(zhǎng)公共前綴

Problem statement:

問(wèn)題陳述：

Write a function to find the longest common prefix string amongst an array of strings.

編寫(xiě)函數(shù)以在字符串?dāng)?shù)組中找到最長(zhǎng)的公共前綴字符串 。

If there is no common prefix, return an empty string "".

如果沒(méi)有公共前綴，則返回一個(gè)空字符串“” 。

Solution:

解：

Input Example:

輸入示例：

Example 1:Let the set of strings to be {"flower", "fly", "flow"}The longest common prefix is "fl"Example 2:Let the set of strings to be {"dog", "donkey", "door", "cat"}The longest common prefix is "", i.e., empty string. Since there is no common prefix at all.

最長(zhǎng)的公共前綴 (Longest common prefix)

Longest common prefix simply means the longest prefix (prefix is a substring also, but not vice-versa) all the member strings consist of.

最長(zhǎng)公共前綴僅表示所有成員字符串組成的最長(zhǎng)前綴(前綴也是子字符串，反之亦然)。

查找一組字符串的最長(zhǎng)公共前綴的算法 (Algorithm to find longest common prefix of a set of strings)

Solving particularly for two string, the problem is not that difficult what it is for a set of strings. But we can simply break the problem into sub-problems where we can solve for only two strings and simply pass the output for further string processing 's. In a simple word, the whole thing can be formulated to be:

特別是對(duì)于兩個(gè)字符串，解決的問(wèn)題并不像一組字符串那么困難。 但是我們可以簡(jiǎn)單地將問(wèn)題分解為幾個(gè)子問(wèn)題，在這些子問(wèn)題中，我們只可以解決兩個(gè)字符串，然后將輸出傳遞給進(jìn)一步的字符串處理。 簡(jiǎn)而言之，整個(gè)事情可以表述為：

LongestCommonPrefix(string1, string2, ..., string n) = LongestCommonPrefix(LongestCommonPrefix(string1,string2),string3,...,string n) = LongestCommonPrefix(newstring1,string3,string4,...,string n) = ... = LongestCommonPrefix(newstring n-1, string n) = new string n = final result So this simply converts the problem for a set of strings to a problem of two strings only

Finding longest common prefix for two strings (string x, string y)

查找兩個(gè)字符串(字符串x，字符串y)的最長(zhǎng)公共前綴

Check for base case

檢查基本情況

IF anyone is empty stringreturn empty string;

Declare result as an empty string;

將結(jié)果聲明為空字符串；

IF string x is smaller than y//check for common prefix part on basis of xFOR( i=0;i<length of string x; i++)IF(x[i]==y[i])result+=x[i]; //append the common characterELSE//no common character at this pointReturnresultEND FORELSE//if string y is smaller than x//check for common prefix part on basis of y FOR (i=0;i<length of y; i++)IF(y[i]==x[i])result+=y[i];//append the common characterELSE//no common character at this pointreturn result;END FOREND IF-ELSE

result consist of longest common prefix for these two strings

結(jié)果由這兩個(gè)字符串的最長(zhǎng)公共前綴組成

Explanation with example

舉例說(shuō)明

Let's consider the first exampleThe set of strings: {"flower", "fly", "flow"}LongestCommonPrefix("flower", "fly", "flow") = LongestCommonPrefix(LongestCommonPrefix ("flower","fly"),"flow") = LongestCommonPrefix("fl", "flow") = "fl"Let's consider the second examplethe set of strings to be {"dog", "donkey", "door", "cat"}LongestCommonPrefix("dog", "donkey", "door", "cat") = LongestCommonPrefix(LongestCommonPrefix ("dog", "donkey"),"door", "cat") = LongestCommonPrefix("do","door", "cat") = LongestCommonPrefix (LongestCommonPrefix("do", "door") , "cat") = LongestCommonPrefix("do", "cat") = "" //empty string .minHeight{min-height: 250px;}@media (min-width: 1025px){.minHeight{min-height: 90px;}} .minHeight{min-height: 250px;}@media (min-width: 1025px){.minHeight{min-height: 90px;}}

C++ implementation

C ++實(shí)現(xiàn)

#include <bits/stdc++.h> using namespace std;string findPrefix(string x,string y){//base case checkingif(x=="" || y=="")return "";string result="";//if string x is smaller than yif(x.length()<y.length()){//check up for common prefix partfor(int i=0;i<x.length();i++){if(x[i]==y[i])result+=x[i];}}else{//if string y is smaller than xfor(int i=0;i<y.length();i++){//check up for common prefix part if(y[i]==x[i])result+=y[i];elsereturn result;}}return result; }string longestCommonPrefix(vector<string>& strs) {//base casesif(strs.size()==0)return "";//if only one string existsif(strs.size()==1)return strs[0];string prefix=strs[0];//follow the associative property for checking //take two strings each time & pass output prefix //as one string for further processingsfor(int i=1;i<strs.size();i++){prefix=findPrefix(prefix,strs[i]);if(prefix=="")return prefix;}return prefix; }int main(){int n;cout<<"enter no of strings you want to add\n";cin>>n;string s;vector<string> v;cout<<"enter "<<n<<" strings\n";//collect inputwhile(n--){cin>>s;v.push_back(s);}//print longest common prefixif(longestCommonPrefix(v)=="")cout<<"no common prefix between the strings\n";elsecout<<"longest common prefix: "<<longestCommonPrefix(v)<<endl;return 0; }

Output

輸出量

First run: enter no of strings you want to add 3 enter 3 strings flower fly flow longest common prefix: flSecond run: enter no of strings you want to add 4 enter 4 strings dog donkey door cat no common prefix between the strings

翻譯自: https://www.includehelp.com/icp/longest-common-prefix.aspx

最長(zhǎng)公共前綴

總結(jié)

以上是生活随笔為你收集整理的最长公共前缀_最长的公共前缀的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。