14. Longest Common Prefix[E]最长公共前缀

左手的ㄟ右手 2021-11-23 07:04 172阅读 0赞

# 题目 #

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 "".  
**Example1：**  
  Input：\["flower","flow","flight"\]  
  Output："fl"  
**Example2：**  
  Input：\["dog","racecar","car"\]  
  Output：""  
  Explanation: There is no common prefix among the input strings.

--------------------

# 思路 #

### 思路一：暴力搜索 ###

本题思路很简单，需要找到最长公共前缀，那么就需要有一个字符串作为基准，在其他字符串中寻找公共字符串。我们以第一个字符串为基准在其他字符串中寻找。寻找的终止条件：

*  当前遍历的长度超过字符串长度
 *  基准字符串的第i个字符与当前字符串第i个字符不匹配。

### 思路二：优化搜索 ###

寻找题目的隐含条件。 需要找的是公共字符串，那么以长度字符串为基准一定能加快程序的速度。此外，我们考虑将字符串数组排序。字符串的排序是按照字母来的，这样做的好处是将公共字符比较多的字符串集中起来，而公共字符比较少的将被放在数组（vector）的两端。例如例1的输入数组\["flower","flow","flight"\]，排序后为：\["flight", "flow", "flower"\]。我们将第一个与最后一个字符串对比，搜寻公共子串。为了防止溢出，以第一个与最后一个长度较短的为基准查找。

--------------------

# Tips #

### Vector（STL） ###

主要是vector容器的begin()、end()和front()、back()函数。

##### （1）begin() #####

返回当前vector容器中起始元素的迭代器。

//定义一个int容器的迭代器 vector<int>::iterator iter; //声明并初始化一个int类型的容器 vector<int> vec={1, 2, 3, 4, 5}; iter = vec.begin(); //返回迭代器表示的元素内容 cout << *iter << endl; //结果为1

##### （2）end() #####

返回当前vector容器中末尾元素的迭代器。注意end()返回的是最后一位的下一位。

//定义一个int容器的迭代器 vector<int>::iterator iter; //声明并初始化一个int类型的容器 vector<int> vec={1, 2, 3, 4, 5}; iter = vec.end() - 1; //end()指向最后一位的下一位 //返回迭代器表示的元素内容 cout << *iter << endl; //结果为5

##### （3）front() #####

返回当前vector容器中起始元素的引用。

//声明并初始化一个int类型的容器 vector<int> vec={1, 2, 3, 4, 5}; //返回迭代器表示的元素内容 cout << vec.front() << endl; //结果为1

##### （4）back() #####

返回当前vector容器中末尾元素的引用。

//声明并初始化一个int类型的容器 vector<int> vec={1, 2, 3, 4, 5}; //返回迭代器表示的元素内容 cout << vec.back() << endl; //结果为5

### List（python） ###

python的列表（List）是序列类型，因此与字符串有一些共同特点，列表与字符串的不同主要在于

*  列表可以包含其他元素，而不仅包含字符。列表可以包含任何类型的元素序列，甚至可以包含不同类型元素混合的序列。
 *  列表是可变类型。

##### （1）创建python列表 #####

List1 = [1, 2, 3, 4, 5] List2 = ['a', 'b', 'c', 'd', 'e'] List3 = [1, 2, 'a', 'b']

##### （2）函数 #####

对于一个列表A

*  **len(A)：**返回列表A的长度，即元素个数。
 *  **min(A)：**返回列表A中的最小元素。如果A是列表的列表，则只考虑每个列表的第一个元素。
 *  **max(A)：**返回列表A中的最大元素。如果A是列表的列表，则只考虑每个列表的第一个元素。
 *  **sum(A)：**返回列表A所有元素的和，A中元素必须是数字。

--------------------

# C++ #

*  思路1

class Solution { public: string longestCommonPrefix(vector<string>& strs) { string s = ""; if(strs.size() == 0) return ""; for(int i = 0; i < strs[0].length();i++) //以第一个元素为基准 { char c = strs[0].at(i); for(int j = 1;j < strs.size();j++) { if(i >= strs[j].length() || strs[j].at(i) != c) return s; } s += c; } return s; } };

*  思路2

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

# Python #

*  思路2

class Solution(object): def longestCommonPrefix(self, strs): """ :type strs: List[str] :rtype: str """ if not strs: return "" if len(strs)==1: return strs[0] minStr = min(strs) maxStr = max(strs) result = "" for i in range(len(minStr)): if minStr[i] != maxStr[i]: return minStr[:i] return minStr

# 总结 #

写代码充分运用

*  公共（以长度最短字符串作为基准）
 *  前缀（利用子字符串方法）

这两个关键字。

# 参考 #

\[1\] [https://www.cnblogs.com/grandyang/p/4606926.html][https_www.cnblogs.com_grandyang_p_4606926.html]

转载于:https://www.cnblogs.com/Jessey-Ge/p/10993475.html

[https_www.cnblogs.com_grandyang_p_4606926.html]: https://www.cnblogs.com/grandyang/p/4606926.html